Finding the Median in Linear Time

  This article is about a Median finding Algorithm. Here we try to find the median element of a List. Let us assume the list is sorted in ascending order then 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 Median 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 Median element of a list. A modified version of Quick Sort called Quick Median is used here. This algorithm takes O(n) time to find the Median 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 to find an approximate Median value which is used as a pivot to divide the list into two. The algorithm Median of Medians will be discussed in a different post.

Advantages:

• Average case running time of O(n).

Disadvantages:

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

To simplify the problem it is assumed that the list contains only odd number of elements and the median is the  ((N+1)/2)^th element in the sorted list.

Click here to download the C Program to find the Median in linear time.
Click here to download the C++ Program to find the Median in linear time.