Worst-case performance of quickSort / getPivot

[Andrei Alexandrescu]

On 11/16/13 6:20 AM, 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?

That may help this particular situation, but does it do anything 
interesting in general?

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

That's done already.

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

Vladimir also enumerated a few disadvantages of random pivot selection. 
I think those notwithstanding, random pivot is an option we should 
consider very seriously. It's easy to use a fast random number 
generators (randomness doesn't need to be very good).

The only reason for which I've hesitated to add random pivot selection 
is that it's less usual and might surprise some. It is _very_ solidly 
motivated.

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

I had a diff at a point that added overloads to sort allowing the called 
to only specify the key. It turned out to be confusing, and all it saved 
was to save a tad of duplication "expr" instead of "expr(a) < expr(b)".


Andrei