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:

• They first arrange the coders in ascending order of ratings and descending order of gold medals.

• 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.

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.

StackExchange Computer Science Q#1231, answer score: 16