On 12/18/12 8:42 PM, Xinok wrote:
On Tuesday, 18 December 2012 at 15:55:17 UTC, Andrei Alexandrescu wrote:
Another approach I wanted to try was to choose the median of K with K
increasing with the size of the array. This is because a good pivot is
more important for large arrays than for small arrays. As such, a
possibility would be to simply sort a stride of the input
(std.range.stride is random access and can be sorted right away
without any particular implementation effort) and then choose the
middle of the stride as the pivot.
If anyone has the time and inclination, have at it!
Perhaps a "median of log n" is in order,
Yah I thought so!
but the trouble is finding an
algorithm for picking the median from n elements. The so called "median
of medians" algorithm can choose a pivot within 30-70% of the range of
the median. Otherwise, there doesn't seem to be any algorithm for
choosing the absolute median other than, say, an insertion sort.
You don't need to choose a median - just sort the data (thereby making
progress toward the end goal) and choose the middle element.
I came up with this clever little guy a while ago which I used in my
implementation of quick sort: http://dpaste.dzfl.pl/b85e7ad8
I would love to enhance it to work on a variable number of elements, but
from what I can comprehend, the result is essentially a partial heap sort.
A very efficient sort for various small fixed sizes is a great
complement for quicksort.
Andrei
