Find n-th smallest element in array without sorting?

Question

I want to write a program to find the n-th smallest element without using any sorting technique..

Can we do it recursively, divide and conquer style like quick-sort?

If not, how?

Answer 1

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

Answer 2

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.

Answer 3

This task is quite possible to complete within roughly O(n) time (n being the length of the list) by using a heap structure (specifically, a priority queue based on a Fibonacci heap), which gives O(1) insertion time and O(log n) removal time).

Consider the task of retrieving the m-th smallest element from the list. By simply looping over the list and adding each item to the priority queue (of size m), you can effectively create a queue of each of the items in the list in O(n) time (or possibly fewer using some optimisations, though I'm not sure this is exceedingly helpful). Then, it is a straightforward matter of removing the element with lowest priority in the queue (highest priority being the smallest item), which only takes O(log m) time in total, and you're finished.

So overall, the time complexity of the algorithm would be O(n + log n), but since log n << n (i.e. n grows a lot faster than log n), this reduces to simply O(n). I don't think you'll be able to get anything significantly more efficient than this in the general case.

Answer 4

You can use Binary heap, if u dont want to use fibonacci heap.

Algo:

1. Contruct the min binary heap from the array this operation will take O(n) time.

2. Since this is a min binary heap, the element at the root is the minimum value.

3. So keep on removing element frm root, till u get ur kth minimum value. o(1) operation

4. Make sure after every remove you re-store the heap kO(logn) operation.

So running time here is O(klogn) + O(n)............so it is O(klogn)...