Selection Algorithm (median of medians ) implementation in C

How do you find out a median of an array? If someone asks you this question, you will immediately say “First sort it and then find the $\left ( \frac{n}{2}\right)^{th}$ element”. Of course, this is correct. But what’s the runtime? hmmm… the lower bound of any comparison based sorting algorithm is a ceiling of $\log_2(n!)$ which is in order of $\Theta(n\log_2n)$. No matter what sorting algorithm do you use, the running time is $\Omega(n\log_2n)$. Can we do better? That is, can we find a median of an array in linear time?. The answer is yes. The following code calculates the median of an array in $O(n)$ time. The algorithm is called ‘Selection algorithm’. This algorithm calculates the ‘$k_{th}$’ smallest value. Median is, therefore, $\left ( \frac{n}{2}\right)^{th}$’ smallest element. The algorithm works as follows: (The code is also available on GitHub).

SHARE Selection Algorithm (median of medians ) implementation in C

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

Share