Find n-th smallest element in array without sorting?

You can find information about that problem here: Selection algorithm.

What you are referring to is the Selection Algorithm, as previously noted. Specifically, your reference to quicksort suggests you are thinking of the partition based selection.

Here's how it works:

• Like in Quicksort, you start by picking a good pivot: something that you think is nearly half-way through your list. Then you go through your entire list of items swapping things back and forth until all the items less than your pivot are in the beginning of the list, and all things greater than your pivot are at the end. Your pivot goes into the leftover spot in the middle.
• Normally in a quicksort you'd recurse on both sides of the pivot, but for the Selection Algorithm you'll only recurse on the side that contains the index you are interested in. So, if you want to find the 3rd lowest value, recurse on whichever side contains index 2 (because index 0 is the 1st lowest value).
• You can stop recursing when you've narrowed the region to just the one index. At the end, you'll have one unsorted list of the "m-1" smallest objects, and another unsorted list of the "n-m" largest objects. The "m"th object will be inbetween.

This algorithm is also good for finding a sorted list of the highest m elements... just select the m'th largest element, and sort the list above it. Or, for an algorithm that is a little bit faster, do the Quicksort algorithm, but decline to recurse into regions not overlapping the region for which you want to find the sorted values.

The really neat thing about this is that it normally runs in O(n) time. The first time through, it sees the entire list. On the first recursion, it sees about half, then one quarter, etc. So, it looks at about 2n elements, therefore it runs in O(n) time. Unfortunately, as in quicksort, if you consistently pick a bad pivot, you'll be running in O(n²) time.