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