C Program to search n-th smallest element in array without sorting?

Question

Hi all,

I wanted to write a program to find the nth smallest element without using any sorting technique..

Can we implement it as a technique used in quick sort, which divides the problem into smaller sub-problems but how is my question..

Please provide some hint..

Thankx

Answer 1

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

Answer 2

Two stacks can be used like this to locate the Nth smallest number in one pass.

• Start with empty Stack-A and Stack-B
• PUSH the first number into Stack-A
• The next number onwards, choose to PUSH into Stack-A only if the number is smaller than its top
• When you have to PUSH into Stack-A, run through these steps
  • While TOP of Stack-A is larger than new number, POP TOP of Stack-A and push it into Stack-B
  • When Stack-A goes empty or its TOP is smaller than new number, PUSH in the new number and restore the contents of Stack-B over it
  • At this point you have inserted the new number to its correct (sorted) place in Stack-A and Stack-B is empty again
  • If Stack-A depth is now sufficient you have reached the end of your search

---

I generally agree to Noldorins' optimization analysis.
This stack solution is towards a simple scheme that will work (with relatively more data movement -- across the two stacks). The heap scheme reduces the fetch for Nth smallest number to a tree traversal (log m).

If your target is an optimal solution (say for a large set of numbers or maybe for a programming assignment, where optimization and the demonstration of it are critical) you should use the heap technique.

The stack solution can be compressed in space requirements by implementing the two stacks within the same space of K elements (where K is the size of your data set). So, the downside is just extra stack movement as you insert.

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

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 5

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)...