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

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

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

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.

This comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by a blog administrator.

ReplyDelete