name of a sorting algorithm

Ian Kelly ian.g.kelly at gmail.com
Tue Feb 14 21:59:00 CET 2012


On Tue, Feb 14, 2012 at 11:10 AM, Jabba Laci <jabba.laci at 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.



More information about the Python-list mailing list