[prog] quick sort using loops

[Jenn Vesperman]

On Sat, 2004-06-26 at 05:23, ed orphan wrote:
> This is  a Linux C question on sorting.
> Can anyone tell me where on the Web I can
> find an a C example of the quick sort
> using loops instead of recursion?
> I understand the quick sort's median of 3
> for the pivot and the idea of partitioning
> the array to be sorted, but I'd like to
> get rid of the recusion so I can see the
> entire logic of it without having to wade
> through the stack. Besides, loops are
> faster and isn't that the whole idea of the
> quick sort?

Whether iteration or recursion is faster is dependant on the
architecture, the compiler's optimisation, your coding, and what exactly
you're trying to achieve.

That said: the quicksort logic for a left-to-right ascending sort is:

1. Grab a number from the list (usually the first).
2. Put everything that's smaller to the left, and everything that's
larger to the right. 
3. Repeat steps 1 and 2 with both the left and the right lists.

As you can see, it's naturally a recursive algorithm. The following is a
pseudocode depiction of it recursively:

quicksort(list) {

   pivotnumber = list(1);
   leftlist = emptylist;
   rightlist = emptylist;

   if (listlength == 1)
      return pivotnumber; /* and exit */
   else
      for (index from 2 to listlength) /* starting from the 2nd item */
         if (list(index) < pivotnumber) then
            leftlist = leftlist + list(index);
         else 
            rightlist = rightlist + list(index);
         endif
      endfor
   endif

   sortedlist = quicksort(leftlist) + compare + quicksort(rightlist);
   return sortedlist;
}


An iterative version basically involves manually keeping track of which
bits you've sorted and which you haven't, whereas the recursive version
doesn't.



If you have access to a good library, Quicksort is on page 113 of Volume
3, of Knuth's 'The art of computer programming'.



Jenn V.
-- 
    "Do you ever wonder if there's a whole section of geek culture 
        	you miss out on by being a geek?" - Dancer.
   My book 'Essential CVS': published by O'Reilly in June 2003.
jenn at anthill.echidna.id.au     http://anthill.echidna.id.au/~jenn/