What is the fastest way to find Nth biggest number of an INT array?

Question

I want a faster function to find the Nth biggest number of an Int array in C#. This function takes N and Array and returns index of that number.

Here is what i have already. It simply sorts the array and then returns the index of that number. It works perfectly but I'm not sure if this is the fastest way. it seems logical to be an algorithm without complete sorting.

static int myFunction(int[] array, int N){
    int[] indexes = new int[array.Length];
    for (int i = 0; i < indexes.Length; i++)
        indexes[i] = i;

    for (int i = 0; i < array.Length; i++)
    {
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[i] < array[j])
            {
                int m = array[j];
                array[j] = array[i];
                array[i] = m;

                m = indexes[j];
                indexes[j] = indexes[i];
                indexes[i] = m;
            }
        }
    }
    return indexes[N];
}

some results :

myFunction(new int[] { 1, 3, 2, 0, 10 }, 0); //returns 4 (index of 10)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 1); //returns 1 (index of 3)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 2); //returns 2 (index of 2)

Answer 1

Randomized quickselect algorithm works in average case complexity O(n). Practically it's very rare to be O(n^2). It uses quicksort's partition function

Answer 2

If your array has a size of a zillion numbers and you need the fifth largest number then you are sorting a lot of numbers that you won't need.

Wouldn't it be faster to keep an ascending sorted sequence of length n (linked list?), and for every element check if it is larger than the first one (which is the smallest in the ascending order

• If smaller: skip to the next element in your large array
• If larger: remove the smallest one from your sorted array which is the first element and insert the larger element in the proper place, keep the array sorted.

After having scanned your complete array, the first element in your sorted sequence is the one you are looking for.

Most comparisons are only with the first element of your sorted array. You'll have to change the array N-times, one time for the N largest numbers. A change of the array is to remove the first element (the smallest) and find the place where to insert the new element to keep the array sorted

Correction: my statement that the array has to be changed N-time is incorrect. This can be seen most easily when offering an array sorted in ascending order: every compared number will be larger than the smallest in the N-size array, and thus cause a replace