A Linear Selection Algorithm

  Here in this article I am writing about a Selection Algorithm. Here we try to find out the N^th element of a List. Let us assume the list is sorted in ascending order then 1st element is the smallest element of the list, the N^th element is the largest in the list and the Median is the ((N+1)/2)^th element if N is odd and elements (N/2) and ((N/2)+1) if N is even. 

  The first method that comes to our mind is to sort the list and then find the N^th element afterwards. We can sort using a quadratic time sorting algorithm like Bubble Sort or Insertion Sort, or better yet we can go for one of the n log n sorts like Heap Sort or Quick Sort. Is this the lower limit for this problem ? The answer is a No. We can have a linear time algorithm to find the N^th element. A modified version of Quick Sort called Quick Select is used here. This algorithm takes O(n) time to find the N^th element in the average case. The only problem with this algorithm is that the worst case time requirement is O(n²). To over come this problem we have to use an algorithm called Median of Medians. The algorithm Median of Medians will be discussed in a different post.

Advantages:

• Average case running time is O(n).

Disadvantages:

• Worst case running time is O(n²).

Click here to download the C Program to perform Selection in linear time.
Click here to download the C++ Program to perform Selection in linear time.