Worst-case performance of quickSort / getPivot

[Vladimir Panteleev]

On Saturday, 16 November 2013 at 14:20:32 UTC, Jean Christophe 
wrote:
> 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?

getPivot sorts the first, middle and last element in the range 
right after it figures out their order. Is there any advantage to 
your suggestion over this?

> 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.

It does, actually - it switches to optimisticInsertionSort for 
ranges of 25 elements or shorter. I disabled that behavior for 
illustration.

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

The impact shouldn't be big if a simple RNG, like LCG or 
XorShift, was used.

> 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?

You mean, sort!`a.foo < b.foo` ?