fastest way to get n lowest from array

Question

I need to find n lowest (which are not 0) from array of doubles (let's call the array samples). I need to do this many times in a loop, thus the speed of execution is crucial. I tried first sorting the array and then taking the first 10 values (which are not 0), however, although Array.Sort is said to be fast, it became the bottleneck:

const int numLowestSamples = 10;

double[] samples;

double[] lowestSamples = new double[numLowestSamples];

for (int count = 0; count < iterations; count++) // iterations typically around 2600000
{
    samples = whatever;
    Array.Sort(samples);
    lowestSamples = samples.SkipWhile(x => x == 0).Take(numLowestSamples).ToArray();
}

Thus I tried a different, but less clean solution, by first reading in the first n values, sorting them, then looping through all other values in samples checking if the value is smaller than the last value in the sorted lowestSamples array. If the value is lower then replace it with the one in the array and sort the array again. This turned out to be approximately 5 times faster:

const int numLowestSamples = 10;

double[] samples;

List<double> lowestSamples = new List<double>();

for (int count = 0; count < iterations; count++) // iterations typically around 2600000
{
    samples = whatever;

    lowestSamples.Clear();

    // Read first n values
    int i = 0;
    do
    {
        if (samples[i] > 0)
            lowestSamples.Add(samples[i]);

        i++;
    } while (lowestSamples.Count < numLowestSamples)

    // Sort the array
    lowestSamples.Sort();

    for (int j = numLowestSamples; j < samples.Count; j++) // samples.Count is typically 3600
    {
        // if value is larger than 0, but lower than last/highest value in lowestSamples
        // write value to array (replacing the last/highest value), then sort array so
        // last value in array still is the highest
        if (samples[j] > 0 && samples[j] < lowestSamples[numLowestSamples - 1])
        {
            lowestSamples[numLowestSamples - 1] = samples[j];
            lowestSamples.Sort();
        }
    }
}

Although this works relatively fast, I wanted to challenge anyone to come up with an even faster and better solution.

Answer 1

This is called a Selection Algorithm.

There are some general solutions on this Wiki page:

http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements

(but you'd have to do a bit of work to convert to c#)

You could use a QuickSelect algorithm to find the nth lowest element, and then iterate through the array to get at each element <= that one.

There's an example QuickSelect in c# here: http://dpatrickcaldwell.blogspot.co.uk/2009/03/more-ilist-extension-methods.html