Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #20407 > unrolled thread

Re: name of a sorting algorithm

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: name of a sorting algorithm Arnaud Delobelle <arnodel@gmail.com> - 2012-02-14 16:22 +0000
    Re: name of a sorting algorithm Den <patentsvnc@gmail.com> - 2012-02-14 08:55 -0800
      Re: name of a sorting algorithm Mel Wilson <mwilson@the-wire.com> - 2012-02-14 12:04 -0500
      Re: name of a sorting algorithm Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-14 10:37 -0700
      Re: name of a sorting algorithm Jabba Laci <jabba.laci@gmail.com> - 2012-02-14 19:10 +0100
      Re: name of a sorting algorithm Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-14 13:59 -0700

#20407 — Re: name of a sorting algorithm

On 14 February 2012 15:31, Dennis Lee Bieber <wlfraed@ix.netcom.com> wrote:
> On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci <jabba.laci@gmail.com>
> wrote:
>
>>Could someone please tell me what the following sorting algorithm is called?
>>
>>Let an array contain the elements a_1, a_2, ..., a_N. Then:
>>
>>for i = 1 to N-1:
>>    for j = i+1 to N:
>>        if a_j < a_i then swap(a_j, a_i)
>>
>        Off hand... The ancient Bubble-Sort...
>
> http://en.wikipedia.org/wiki/Bubble_sort

Ahem...

No, it's not Bubble Sort.  Bubble sort only swaps adjacent terms.

I don't know what this sort is called, if it even has a name.  It's a
kind of Selection Sort, as each pass it looks for the minimum of the
remaining unsorted items.  But it ruffles the unsorted list each pass,
seemingly to save using an extra register to store the current minumum
(there was a time when registers were at a premium).

-- 
Arnaud

[toc] | [next] | [standalone]

#20409

On Feb 14, 8:22 am, Arnaud Delobelle <arno...@gmail.com> wrote:
> On 14 February 2012 15:31, Dennis Lee Bieber <wlfr...@ix.netcom.com> wrote:
>
> > On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci <jabba.l...@gmail.com>
> > wrote:
>
> >>Could someone please tell me what the following sorting algorithm is called?
>
> >>Let an array contain the elements a_1, a_2, ..., a_N. Then:
>
> >>for i = 1 to N-1:
> >>    for j = i+1 to N:
> >>        if a_j < a_i then swap(a_j, a_i)
>
> >        Off hand... The ancient Bubble-Sort...
>
> >http://en.wikipedia.org/wiki/Bubble_sort
>
> Ahem...
>
> No, it's not Bubble Sort.  Bubble sort only swaps adjacent terms.
>
> I don't know what this sort is called, if it even has a name.  It's a
> kind of Selection Sort, as each pass it looks for the minimum of the
> remaining unsorted items.  But it ruffles the unsorted list each pass,
> seemingly to save using an extra register to store the current minumum
> (there was a time when registers were at a premium).
>
> --
> Arnaud

I disagree.  In a bubble sort, one pointer points to the top element,
while another descents through all the other elements, swapping the
elements at the pointers when necessary.  Then the one pointer moved
down to the next element and the process repeats.  This looks like the
bubble sort to me.  It was one of the first algorithms I had to
program in my first programming class in 1969.

Den

[toc] | [prev] | [next] | [standalone]

#20410

Den wrote:

> I disagree.  In a bubble sort, one pointer points to the top element,
> while another descents through all the other elements, swapping the
> elements at the pointers when necessary.

'When I use a word,' Humpty Dumpty said, in rather a scornful tone, 'it 
means just what I choose it to mean — neither more nor less.' (_Through the 
Looking Glass, Lewis Caroll).  And you, too, have that ability.  
Contrariwise see Knuth, _The Art of Computer Programming_ Section 5.2.2, 
Algorithm B.

	Mel.
	

[toc] | [prev] | [next] | [standalone]

#20412

On Tue, Feb 14, 2012 at 9:55 AM, Den <patentsvnc@gmail.com> wrote:
> On Feb 14, 8:22 am, Arnaud Delobelle <arno...@gmail.com> wrote:
>> On 14 February 2012 15:31, Dennis Lee Bieber <wlfr...@ix.netcom.com> wrote:
>>
>> > On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci <jabba.l...@gmail.com>
>> > wrote:
>>
>> >>Could someone please tell me what the following sorting algorithm is called?
>>
>> >>Let an array contain the elements a_1, a_2, ..., a_N. Then:
>>
>> >>for i = 1 to N-1:
>> >>    for j = i+1 to N:
>> >>        if a_j < a_i then swap(a_j, a_i)
>>
>> >        Off hand... The ancient Bubble-Sort...
>>
>> >http://en.wikipedia.org/wiki/Bubble_sort
>>
>> Ahem...
>>
>> No, it's not Bubble Sort.  Bubble sort only swaps adjacent terms.
>>
>> I don't know what this sort is called, if it even has a name.  It's a
>> kind of Selection Sort, as each pass it looks for the minimum of the
>> remaining unsorted items.  But it ruffles the unsorted list each pass,
>> seemingly to save using an extra register to store the current minumum
>> (there was a time when registers were at a premium).
>>
>> --
>> Arnaud
>
> I disagree.  In a bubble sort, one pointer points to the top element,
> while another descents through all the other elements, swapping the
> elements at the pointers when necessary.  Then the one pointer moved
> down to the next element and the process repeats.  This looks like the
> bubble sort to me.  It was one of the first algorithms I had to
> program in my first programming class in 1969.

Either you're misremembering, or the algorithm you programmed 43 years
ago was not actually bubble sort.  Quoting from Wikipedia:

"""
Bubble sort, also known as sinking sort, is a simple sorting algorithm
that works by repeatedly stepping through the list to be sorted,
comparing each pair of adjacent items and swapping them if they are in
the wrong order. The pass through the list is repeated until no swaps
are needed, which indicates that the list is sorted. The algorithm
gets its name from the way smaller elements "bubble" to the top of the
list.
"""

In the present algorithm, you'll note that elements in the unsorted
part of the list do not "bubble up" as they would in bubble sort.
Rather, they jump around somewhat randomly until they are finally
selected for the current sort index.  I agree with Arnaud -- this is a
selection sort variant that saves a local variable (the index of the
minimum element) by placing it at the current sort index instead -- at
the cost of doing additional swaps.  Probably not a good trade-off in
Python (but then again, no pure Python sort algorithm is likely to
perform better than the built-in).

Cheers,
Ian

[toc] | [prev] | [next] | [standalone]

#20414

Hi,

> Either you're misremembering, or the algorithm you programmed 43 years
> ago was not actually bubble sort.  Quoting from Wikipedia:
>
> """
> Bubble sort, also known as sinking sort, is a simple sorting algorithm
> that works by repeatedly stepping through the list to be sorted,
> comparing each pair of adjacent items and swapping them if they are in
> the wrong order. The pass through the list is repeated until no swaps
> are needed, which indicates that the list is sorted. The algorithm
> gets its name from the way smaller elements "bubble" to the top of the
> list.
> """

I don't agree with the last sentence. During bubble sort, in the 1st
pass the largest element is moved to the top (for me "top" means the
right side (end) of an array). Thus the end of the array is sorted. In
the 2nd pass, the largest element of the unsorted left part is moved
to the end, etc. That is, it's the _larger_ elements that bubble to
the top. At http://en.wikipedia.org/wiki/Bubble_sort you can find an
animated gif that shows how the algorithm works.

> In the present algorithm, you'll note that elements in the unsorted
> part of the list do not "bubble up" as they would in bubble sort.
> Rather, they jump around somewhat randomly until they are finally
> selected for the current sort index.  I agree with Arnaud -- this is a
> selection sort variant that saves a local variable (the index of the
> minimum element) by placing it at the current sort index instead -- at
> the cost of doing additional swaps.  Probably not a good trade-off in
> Python (but then again, no pure Python sort algorithm is likely to
> perform better than the built-in).

The minimum selection sort is an improvement of this "noname"
algorithm. I give it in pseudo-code. Let A be an array with N
elements. Indexing starts with 1.

for i := 1 to N-1:
    minindex := i
    for j := i+1 to N:
        if A[j] < A[minindex] then minindex := j
    end for
    if i != minindex then swap(A[i], A[minindex])
end for

The two loops are the same as in the naive version. It will also sort
the array from the left side. It does much less swaps than the naive
version.

If the "noname" algorithm is called "selection sort", then its name
can be misleading. One may ask "OK, but which one? Minimum or maximum
selection sort?". Well, neither...

Laszlo

[toc] | [prev] | [next] | [standalone]

#20418

On Tue, Feb 14, 2012 at 11:10 AM, Jabba Laci <jabba.laci@gmail.com> wrote:
> Hi,
>
>> Either you're misremembering, or the algorithm you programmed 43 years
>> ago was not actually bubble sort.  Quoting from Wikipedia:
>>
>> """
>> Bubble sort, also known as sinking sort, is a simple sorting algorithm
>> that works by repeatedly stepping through the list to be sorted,
>> comparing each pair of adjacent items and swapping them if they are in
>> the wrong order. The pass through the list is repeated until no swaps
>> are needed, which indicates that the list is sorted. The algorithm
>> gets its name from the way smaller elements "bubble" to the top of the
>> list.
>> """
>
> I don't agree with the last sentence. During bubble sort, in the 1st
> pass the largest element is moved to the top (for me "top" means the
> right side (end) of an array). Thus the end of the array is sorted. In
> the 2nd pass, the largest element of the unsorted left part is moved
> to the end, etc. That is, it's the _larger_ elements that bubble to
> the top. At http://en.wikipedia.org/wiki/Bubble_sort you can find an
> animated gif that shows how the algorithm works.

I think that by "top" they mean "front".  Each largest element in turn
gets moved to the end in a single pass.  It is the smaller elements
gradually moving toward the front over many passes that I believe is
described as "bubbling", as can be seen in that gif.

> If the "noname" algorithm is called "selection sort", then its name
> can be misleading. One may ask "OK, but which one? Minimum or maximum
> selection sort?". Well, neither...

It is a minimum selection sort, because it selects the minimum element
on each pass.  It just stores the minimum element so far in-place in
the array, rather than in a separate variable.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web