A question about sort stable

[kyle york]

Keith Thompson wrote:
.... snip ...

I don't think so, without using auxiliary data (such as indices).
I am prepared to be proven wrong on this.

If, in the comparison routine, one was to compare the pointers if the
other data compare equal that would make it stable, yes?

At least that's my reading of 6.5.8.5

 

[CBFalconer]

.... snip ...

Strictly you are right. However if a function called qsort()
doesn't implement quicksort then you ought to send it back.

Why? Maybe the implementor wants to guarantee the worst case
execution time? Bye bye quicksort.

 

[Keith Thompson]

Strictly you are right. However if a function called qsort() doesn't
implement quicksort then you ought to send it back.

Why? There are plenty of good sorting algorithms other than
Quicksort. Why shouldn't qsort() use one of them?

 

[Richard Tobin]

Strictly you are right. However if a function called qsort() doesn't
implement quicksort then you ought to send it back.

It's unfortunate that C's sort function is called qsort(). But most
implementations use something better than vanilla quicksort, and I'd
be more inclined to send it back if it didn't.

-- Richard

 

[user923005]

Strictly you are right. However if a function called qsort() doesn't
implement quicksort then you ought to send it back.- Hide quoted text -

Most modern qsort() functions do not use the quicksort algorithm
(though quicksort is in the bag of tricks).
For most implementations that I have seen, it is a hybrid algorithm
that works (roughly speaking) like this:
If the partition is small, then use insertion sort.
If the partition is large, then subdivide the partition (typical
quicksort method)...
However -- if the number of subidivisions is already at log(n) then we
have a perverse data set, so switch to heapsort.

The idea of using insertion sort when the set is not big is due to
Richard Singleton (ACM algorithm 347).
The idea of using heapsort when the sort goes perverse is called
Introspective sort. Introspective sort is due to David Musser:
http://www.cs.rpi.edu/~musser/gp/introsort.ps

 

[Joe Wright]

Why? There are plenty of good sorting algorithms other than
Quicksort. Why shouldn't qsort() use one of them?

Please nominate an in place array sort for qsort() quicker than the
quicksort. I like insertion sorts and especially Shell sorts because
they are simpler. But they are not quicker.

 

[Keith Thompson]

Please nominate an in place array sort for qsort() quicker than the
quicksort. I like insertion sorts and especially Shell sorts because
they are simpler. But they are not quicker.

There are a number of O(n log n) sorting algorithms. I haven't
studied them recently enough to make any definitive statements, but
Mergesort and Heapsort are two examples.

Naive Quicksort is O(n**2), but that's not hard to correct.

 

[CBFalconer]

.... snip ...


There are a number of O(n log n) sorting algorithms. I haven't
studied them recently enough to make any definitive statements,
but Mergesort and Heapsort are two examples.

Naive Quicksort is O(n**2), but that's not hard to correct.

It is impossible for all possible inputs. There is always a worst
case.

And the optimum depends highly on the size of the sortee. For
example, sorting the array a = [2, 1] involves only one comparison
and one-half (avg) exchange. Setting up and tearing down a more
sophisticated sort takes time and effort.

 

[Malcolm McLean]

If, in the comparison routine, one was to compare the pointers if the
other data compare equal that would make it stable, yes?

At least that's my reading of 6.5.8.5

You can't compare the pointers passed to you by qsort() because the way it
works is to randomly select one item as a "pivot", move it to the lowest
place, and then run through the array putting all the items above the pivot
to the top and below the pivot to the bottom. The pivot is always the top of
the "bottom" heap. The pivot is now in the right place and you have two
unsorted arrays above and below it. So it then calls itself recursively on
those two arrays until the array length goes to one.

Here's a version I wrote. bubblesort() and swap() do what you would expect.
I can't see an easy way to undo the swapping of data items to make the sort
stable, without gobbling lots of extra memory.

/*
quicksort - quicksort algorithm
Params: ptr - base of array
N - number of items
sz - width of each item
comp - comparision function
*/
void quicksort(void *ptr, int N, int sz, int (*comp)(const void *e1, const
void *e2))
{
int pivot = 0;
int left = 1;
int right = N;
unsigned char *xptr = ptr;

if(N < 8)
{
bubblesort(ptr, N, sz, comp);
return;
}
else
{
swap(xptr, xptr + (N/2) * sz, sz);
while(left < right)
{
if ( (*comp)(xptr + left * sz, xptr + pivot * sz) <= 0)
{
left++;
}
else
{
right--;
swap(xptr + left * sz, xptr + right * sz, sz);
}
}
left--;
swap(xptr, xptr + left * sz, sz);
quicksort(xptr, left, sz, comp);
quicksort(xptr + (left + 1) * sz, N - left - 1, sz, comp);
}
}

 

[Richard Harter]

It is impossible for all possible inputs. There is always a worst
case.

This isn't quite true. The thing is, quicksort is actually a family of
algorithmts. In pseudo code the algorithm is:

function quicksort(data)
choose a pivot
partition data into left and right
sort left
sort right

There are various details and fiddles, e.g., fat pivot, sort the smaller
partition first, etc., but the thing that determines whether a
particular implmentation is worst case O(n**2) is how you choose the
pivot. Rather generally, the cost of choosing a "good" pivot is O(n),
where a "good" pivot choice algorithm is one that guarantees that the
quicksort implementation worst case performance is O(n* log n).

The difficulty is that the cure is ususally worse than the disease.

And the optimum depends highly on the size of the sortee. For
example, sorting the array a = [2, 1] involves only one comparison
and one-half (avg) exchange. Setting up and tearing down a more
sophisticated sort takes time and effort.

 

[user923005]

Please nominate an in place array sort for qsort() quicker than the
quicksort. I like insertion sorts and especially Shell sorts because
they are simpler. But they are not quicker.

Weak heapsort is faster (but requires N additional bits of storage,
and therefore is not totally 'in place')
http://www.springerlink.com/content/x442k4973j5242p0/

Related, very intersting paper:
"Implementing HEAPSORT with n log n -0.9n and QUICKSORT with n log n +
0.2n Comparisons"
Stefan Edelkamp, Patrick Stiegeler
You can find the source code for this project here:
http://www.jea.acm.org/CODE/Vol7Nbr5.tar

For integers, you can sort in n* log(log(n))
http://www.nada.kth.se/~snilsson/public/papers/sortDobbs/

These look interesting:
"A Heap-Based Optimal Inversions-Sensitive Sorting Algorithm"
Srinath Sridhar

The papers on generalized quicksort and on presorting also look very
interesting.

Of course, for multiple CPU/multiple disk systems, everything changes
and some other algorithms dominate.