Most efficient way to find the nth highest number in an array?

Question

I am wondering if this is the most efficient way to find the nth highest number in an unsorted array. What I did was sort it with mergeSort then find the index of the nth highest number. I think this is more efficient than most searches but I am not quite sure.....

import java.util.Arrays;
public class ThirdHighest {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int [] a = new int[]{3,5,6,7,8,2,1,10,9};
    System.out.print(Arrays.toString(a));
    mergeSort(a);
    System.out.print(Arrays.toString(a));
    System.out.print(nHighestValue(a, 3));

}
public static void mergeSort(int[] arr) {
    if(arr.length > 1) {
        int lengthLeft = arr.length / 2;

        int [] left = Arrays.copyOfRange(arr, 0, lengthLeft);
        int [] right = Arrays.copyOfRange(arr, lengthLeft, arr.length);
        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }
}
public static void merge(int[] result, int[] left, int[] right){
    int l1 = 0;
    int r2 = 0;
    while(l1 < left.length || r2 < right.length) {
        if(l1 == left.length) {
            result[l1+r2] = right[r2];
            r2 += 1;
        } else if(r2 == right.length){
            result[l1+r2] = left[l1];
            l1 += 1;
        } else if(left[l1] < right[r2]) {
            result[l1 + r2] = left[l1];
            l1 += 1;
        } else {
            result[l1+r2] = right[r2];
            r2 += 1;
        }
    }
}
public static int nHighestValue(int[] a, int n) {
    int index = a.length - n;
    return a[index];

}

}

Sorting is O(n log n). I think this can be done in O(k*n). – HectorLector Feb 02 '14 at 21:55 — HectorLector, Feb 02 '14 at 21:55
Damn my first question on stack and it sucks! :( – DrJonesYu Feb 02 '14 at 22:12 — DrJonesYu, Feb 02 '14 at 22:12

score 1 · Accepted Answer · answered Feb 02 '14 at 22:09

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

answered Feb 02 '14 at 22:09

chrk

4,037
2
39
47

score 0 · Answer 2 · answered Feb 02 '14 at 21:54

Finding the lowest or highest from unodrered data can be done in O(n), as @alitereralmind demonstrates.

Finding the Nth highest (as requested) is more complicated, since you need to track the best candidates. That turns the scan into an N-deep insertion sort with values which aren't within the top N falling out the end. While that might be more efficient than doing a full sort, I'm not sure it's worth the additional coding effort on normal-sized problems... especially if a similar query might be issued again and the initial sort could be reused.

Most efficient way to find the nth highest number in an array?

2 Answers2