# Efficiently selecting the median and elements to its left and right

Suppose we have a set $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ of $N$ coders.

Each Coders has rating $R_i$ and the number of gold medals $E_i$, they had won so far.

A Software Company wants to hire exactly three coders to develop an application.

For hiring three coders, they developed the following strategy:

1. They first arrange the coders in ascending order of ratings and descending order of gold medals.
2. From this arranged list, they select the three of the middle coders. E.g., if the arranged list is $(a_5,a_2,a_3,a_1,a_4)$ they select $(a_2,a_3,a_1)$ coders.

Now we have to help company by writing a program for this task.

Input:

The first line contains $N$, i.e. the number of coders.

Then the second line contains the ratings $R_i$ of $i$th coder.

The third line contains the number of gold medals bagged by the $i$th coder.

Output:

Display only one line that contains the sum of gold medals earned by the three coders the company will select.

• So higher-rated coders always win fewer medals?? If not, what order are you actually using to sort? – JeffE Apr 12 '12 at 19:04

This is a problem of selecting the $k$th smallest element from the list solved by a class of algorithms called the Selection Algorithms. There exist deterministic linear time selection algorithms so your problem can be solved in linear time by selecting the $n/2,n/2-1,n/2+1$th smallest elements from the original unsorted list.

• If you'd like, you can run the selection algorithm once to find the median, and then find the minimum and maximum in the right and and left partitions respectively in one swoop. – Zach Langley Apr 12 '12 at 17:51
• @Sid @ Zach Langley Hi can you please provide the Pseudo Code .i Went through wiki paedia but feels a bit tough to understand.So can you please provide the PseudoCode Thanks a lot! – Jack Apr 12 '12 at 18:00
• @Jack are you familiar with how quicksort works? The randomized selection algorithm is essentially the same, except it only recurses on one side of each pivot. – Zach Langley Apr 12 '12 at 18:03
• @Jack: The wikipedia article on selection algorithms (linked in Sid's answer) contains pseudocode. Google also works. – JeffE Apr 12 '12 at 19:05
• @Sid :: I read the wiki algorithm (Partition-based general selection algorithm) .Do we have to call select function three times with k=n/2 ,k=n/2-1,k/2.Also what will be the value of left,right while calling function select.Also in partition function,what will be the val of partition Index. – Jack Apr 13 '12 at 3:18