2
$\begingroup$

I am working with small data sets of N elements, usually with N = 8, 16, or 32 elements; all are positive 64-bit float numbers. I need to identify the smallest N/2 elements. It is not required that the smallest N/2 elements be sorted, just that I identify which ones they are from among the group of N. Each program run must perform this sort up to a billion times, so sort speed improvements could generate useful returns for me. Right now I am using a simple Quicksort that orders all N elements just to prove out my concept.

It is quite likely that my data are not randomly distributed, but I am not yet at the point where I can get a handle on that.

Eventually, the grand design is that this will find its way into the real world via an X-code implementation.

Any recommendations as to what my best sorting strategy ought to be?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Run a micro-benchmark. Which library implementation wins? (Note: most already use "the best" algorithm for small $n$, anyway.) See also this related question. $\endgroup$
    – Raphael
    Commented Jul 23, 2015 at 7:21

2 Answers 2

Reset to default
3
$\begingroup$

Here are two ideas. It's hard to say whether they're any good - you'll have to implement them.

  1. Use (randomized or deterministic) QuickSelect in order to find the median, and then find the bottom half with a single scan.

  2. Use some hard-coded sorting network, e.g. Batcher, bitonic or pairwise. If there is some hardware support for the basic operation of sorting two memory cells, then this can be pretty fast (even though you're not using parallelism). You can also try to come up with your own sorting network that only sorts in your sense - perhaps trimming one of the ones I listed would do.

Improve this answer
$\endgroup$
3
  • $\begingroup$ My favoured line of thinking is to use some kind of efficient sort to find the median, after which one pass through Quicksort will give me the output I need. I lack the mathematical chops, though, to be able to determine a priori if that is more efficient than some other method. $\endgroup$
    – Richard M
    Commented Feb 2, 2015 at 23:28
  • $\begingroup$ Modifying a hard-coded network sounds interesting. I hadn't thought of that. Looking at it with an empty mind, though, it isn't obvious to me what rationale I might employ to modify the logic to be of help, but let me chew it over. $\endgroup$
    – Richard M
    Commented Feb 2, 2015 at 23:31
  • $\begingroup$ "one run through Quicksort" is one linear-time partitioning. If you need the result in-place, that's probably a good idea. If you need or can live with a copy, just do a linear scan as Yuval proposes. $\endgroup$
    – Raphael
    Commented Jul 23, 2015 at 7:25
2
$\begingroup$

You can modify your quicksort to a quickselect for the $N/2$ position.

Also, try implementing your own insertion sort. Insertion sort is REALLY fast for small arrays, and may be even faster than the quickselect.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Following Yuval, I am currently using a "trimmed" bitonic (the penultimate stage of the bitonic actually represents the specific result I am looking for). Although this measures as the fastest of the algorithms I have tried so far, the differences are surprisingly marginal. I will try the insertion sort soon and see how that compares. But I'm not sure I can see a "trimming" opportunity there. $\endgroup$
    – Richard M
    Commented Jul 23, 2015 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.