Monday, 3 December 2012

A Linear Selection Algorithm

  Here in this article I am writing about a Selection Algorithm. Here we try to find out the Nth 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 Nth 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 Nth 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 Nth element. A modified version of Quick Sort called Quick Select is used here. This algorithm takes O(n) time to find the Nth element in the average case. The only problem with this algorithm is that the worst case time requirement is O(n2). 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.

  • Average case running time is O(n).
  • Worst case running time is O(n2).

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.

No comments:

Post a Comment