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

Groups > comp.lang.python > #20414

Re: name of a sorting algorithm

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next 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