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.^{2})**Advantages:**

- Average case running time is
**O(n).**

**Disadvantages:**

- Worst case running time is
**O(n**^{2}).

## No comments:

## Post a Comment