Re: quick sort

Malcolm McLean wrote:
<sophia.agnes@xxxxxxxxx> wrote in message
Dear all,

The following is the quick sort function which i have seen in my note
book
how good is this function ?
[... code snipped; see up-thread ...]

First, define "good."

One peculiarity that stands out about this version is its
choice of which elements to swap. Consider what happens, for
example, if the first part of the array is nicely jumbled but
the latter part contains only large numbers, all larger than
the pivot. Whenever you find a large number near the beginning,
you swap it to the current end, thus bringing a large value
toward the beginning of the array. At the next iteration you
swap that value back to the new endpoint and bring yet another
large value toward the beginning. Roughly speaking, you put
all the large values near the end through a sort of square dance
whose effect is just to move them one place leftward.

The usual scheme is to increment `l' until it reaches an
out-of-position value, then to decrement `r' until it, too,
reaches an out-of-position value, and then to swap those two
values. You don't need all those other swaps; I don't think
they'll hurt the sort's correctness, but they'll burn CPU time
unnecessarily.

As a "pure" Quicksort, your function is prone to behave badly
on some inputs that would seem easy: an array that's already in
ascending or descending order, for instance. Also, when sort()
calls itself to sort the two pieces, it's a good idea to sort the
shorter piece before the longer; that limits the recursion depth
to the log of the array length, instead of risking trying to make
as many calls as there are elements.

Also when the arrays get very small you can often speed things up by using a bubblesort, which has fewer overheads.

Ick. Bubblesort is not only slower than straight insertion,
but more complicated to boot. The only situation I can think of
where bubblesort might be appropriate is when you have an array
that is known to be "almost sorted," with just a few close-together
elements out of order. That's not the case here; don't use it.

--
Eric Sosman
esosman@xxxxxxxxxxxxxxxxxxxx
.

Relevant Pages

  • Re: Sort Two Dimensioanl Array
    ... Does Chris' Bubble Sort work - works in 2003 Autotext. ... Sort the given array into order. ... Optional SortAscending As Boolean = True) ... Dim BubbleSort As Long ...
    (microsoft.public.word.vba.general)
  • Re: Help me with references
    ... >> efficiently than you can with bubble sort. ... > Bubblesort accomplishes this faster than insertion sort. ... your "almost sorted array" with one comparison. ...
    (comp.lang.java.help)
  • Re: "Sorting" assignment
    ... And many others prefer to call partition exchange because "quicksort" ... bin B depending on whether it is greater than, ... If the array is already sorted, this means that you end up ... attempt to sort them. ...
    (comp.programming)
  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • Re: problem in solving this.
    ... element is selected and placed at the end of the array. ... It looks like bubble sort to me. ... One swap per pass. ...
    (comp.lang.fortran)