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

Groups > comp.lang.python > #20418

Re: name of a sorting algorithm

Show all headers | View raw

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.

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web