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
