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

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

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