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
