name of a sorting algorithm
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:
>> 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
> 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