Worst-case performance of quickSort / getPivot

[Jean Christophe]

On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev 
wrote:

> getPivot(0..10)
> 8,7,6,5,4,3,2,1,0,9 <- getPivot - before swap
> 9,7,6,5,4,8,2,1,0,3 <- getPivot - after swap
> 9,7,6,5,4,3,2,1,0,8 <- quickSortImpl - after swap
> 9,8,6,5,4,3,2,1,0,7 <- quickSortImpl - after partition
> getPivot(2..10)
> 6,5,4,3,2,1,0,7 <- getPivot - before swap
> 7,5,4,3,6,1,0,2 <- getPivot - after swap
> 7,5,4,3,2,1,0,6 <- quickSortImpl - after swap
> 7,6,4,3,2,1,0,5 <- quickSortImpl - after partition
> (...)

One possible implementation suggests to swap Left and Right 
immediatly after choosing the Pivot (if Left > Right), then place 
the Pivot at Right-1. It seems that this option was not taken. 
Any reason?

As the efficiency of Quicksort is known to be bad in sorting a 
small number of elements, ie. < 10, it might be nice to implement 
an option to automatically switch to a more appropriate algorithm 
if it's relevant to do so.

> * Many sources recommend using a random element as a pivot. 
> According to [2], "Randomized quicksort, for any input, it 
> requires only O(n log n) expected time (averaged over all 
> choices of pivots)".

IMO it would be costly and not so relevant if the goal is to be 
fast.

> Also, if it is not possible to predict the pivot choice, it is 
> impossible to craft worst-case input, which is a plus from a 
> security point[3]. However, I'm not sure if making the behavior 
> of std.algorithm's sort nondeterministic is desirable.

I think it's not desirable.

--

Quicksorting a collection of Objects?

BTW I'm very interested in finding a library which could 
Quicksort an array of pointers, where each pointer points to a 
class object (or a structure) address. The library would make 
possible, for example, to sort the `class objects` using one of 
their members as the key. Because the swaps are done on the 
actual pointers (and not the Objects pointed), the Quicksort 
should be very efficient. However, the algorithm woulnd't be so 
trivial to implement because each comparison shall be done using 
the Object's member's value :

eg. Obj1.foo < Obj2.foo.

Of course, the programmer can choose any relevant member property 
to sort the collection. And it should be as easy to use as:

class SomeClass { string foo; double bar;}
SomeClass[] a;
// put 100 000 objects into a
a.sort("foo");

Do we already have something like that available somewhere or is 
it possible to make one eventually?

-- JC