BW>  TM> If you think that bubble sort is a good sorting algorithm, I  h
BW>  TM> object.
BW> If you have a better one, then why not share it?  For the price of a
Agreed.  Quicksort is very popular because of its speed and because it
is available through the Standard C  function  qsort().  I  think  the
Standard  C++  function  template  sort() is required to have the same
performance characteristics, which will make it  faster  than  qsort()
because  there  is  no need to dereference a function pointer for each
comparison.
The idea of quicksort is:
Rearrange your list such that one element (usually the one that was in
front originally) is at the right place, and all elements in front  of
it are smaller and all elements behind it are larger.
Then apply quicksort recursively to the sublists before and after that
element.
The  rearrangement is done by iterating from both ends of the list and
swapping the positions of elements that are on the wrong side.
In C++, this might look like this:
template 
quicksort(Iterator head, Iterator tail)
{
    if (head==tail) return;    // empty list is always sorted
    Iterator first = head,
             last = tail;
    if (++first==last) return;  // single element list is alway sorted
    --last;
    
    while (first!=last)        
    {
        // try to find an element smaller than *head from the end
        while (last!=first && *last>=*head)
            --last;
        // try to find an element larger than *head from the front
        while (first!=last && *first<=*head)
            ++first;
        if (first!=last) 
            // we've found them, so let's swap them
            swap(*first,*last); 
    }
    // No first==last reference an element <= *head. All elements beyond      
   
    // first are no smaller than *head, and all elements before first     
    // are no larger than *head, so first is the position of *head in     
    // the sorted list. Let's move it there:
    swap(*head,*first); 
    // Now sort the beginning and the end
    quicksort(head,--first);
    quicksort(++last,tail);
}
This code isn't tested!! Would somebody please proofread?
The function template takes two arguments of a type (such as a pointer
type and a Standard C++ Library bidirectional iterator type) that  can
be dereferenced to an element type that can be assigned and compared:
If you have a C-style array
char myName[7];
initialized using
strcpy(myName,"Thomas");
you can sort it using
quicksort(myName, myName + strlen(myName))
The result should be something like "Tahmos".
Note that the second argument to quicksort() refers  to  "one  element
past the structure".
Thomas
---
 þ MM 1.0 #0113 þ Who is General Failure and why is he reading my disk?
---------------