On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei
Alexandrescu wrote:
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
A while ago in another thread about sorting I believe you
mentioned the possibility of having templated sorting networks
for small numbers of items, did that idea come to anything?
