Write a C program to find kth largest elements in array in c ( from given unordered list or array). For example if given list is 2,3,4,5,12,8,10,6,20,7,21, 22 ,25 ,24,14 then 3rd largest element is 22.

Method (1)

The first method which is not an optimal solution is sort the array and return the kth element. sorting would take O(NlogN) complexity where N is the size of array. After sorting list would be 25  24  22  21  20 14 12 10 8 7 6 5 4 3 2 and hence 3rd largest is 22. 

Method (2)

Using medians of median algorithm to find kth largest element.

Step 1 : Divide the list into N/5 lists of 5 elements each .
Step 2 : Find the median in each sub list of 5 elements .
Step 3 : Recursively find the median of all the medians , call it M.
Step 4 : Partition the list into unique elements larger than M ( call this sublists L1 ) and those no longer than m ( call
this sublists L2 ,list L2 include M also ) .
Step 5 : If K<=|L1| , return Selecton (L1 , K ) .
Step 6 : If K−1=|L1| , return M .
Step 7 : If K>=|L1|+1 , return Selection (L2 ,K−|L1| −1 ).

Now let us apply above steps on 2,3,4,5,12,8,10,6,20,7

  • Divide the list into N/5 , where N is size of list ( 10/5=2 ).

2  3  4  5  12             8  10   6   20  7            21   22   25   24 14

  • After dividing the list into groups of 5 elements in each, find the median element in each list. Median is marked here in red.

2  3  4  5  12            8  10   6   20  7           21   22   25   24 1

   Here  4   6   25  is median of above sublists.

  • After finding medians in each sublist, find median of medians.

  4   6   25    ( 6 is median  in 4 6 25)

  • Now consider 6 ( medians of median ) to be pivot element and divide the list (2,3,4,5,12,8,10,6,20,7,21, 22 ,25 ,24,14) into two groups one which is greater than 6 and another which is less than 6.

L2 = [  2  3  4  5  6]     and   L1 = [ 12  8  10  20   7   21   22   25  24  14 ]  

        size of L2 is 5           and  size of L1 is  10

  • Now we have to find 3rd largest element. As from step step 5 , k=3 , k <= | L1 | then return selection(L1, K). we need to discard list L2 and pivot element 6. After this step divide the list into groups of 5 again ,find the medians and then find the medians of median.

      L1 = [ 12  8  10  20   7   21   22   25  24  14 ]

            12  8  10   20    7        and       21    22    25   24   14

            list of median  10   25

            Here there are two medians 10 and 25. In this case we can choose any one of them. Let us choose 10 as pivot element.

  • Now consider 10 ( medians of median ) to be pivot element and divide the list 12  8  10  20   7   21   22   25  24  14  into two groups one which is greater than 10 and another which is less than 10.

L2 = [ 8   7  10] and L1= [12  20  21  22   25  24  14]

  • As from step k(3) <= |L1| , then return selection(L1,K). we need to discard list L2 and pivot element 10. After this we again divide the list  12  20  21  22   25  24  14 into groups of 5 and find the medians and then median of medians.

12  20  21   22  25 ] and   [ 24  14 ]

          medians   are    21  24  14

          median of medians is 24

  • Now we need to divide the list 12  20  21  22   25  24  14  into two sublists, one which is less than 24 and one which is greater than 24.

L2 = [ 12  20  21  22 14  24]   and L1 = [  25 ]

  • Go to step 5 , k(3) <= | L1 | fails , as the 3 is greater than size of L1, but K >= |L1| + 1,then return selection(L2, K-|L1|-1) now K = K – |L1| – 1 = 3 – 1 – 1 = 1. 
  • Now we have remaining list 12 20 21 22 14. and K = 1. 
  • Divide the list into groups of 5 , find medians and median of median.

12  20  21  22   14

          Here 21 is only median and hence it will be medians of median also.

  • Now divide the list into two sublists. one which is less than 21 and another which is greater than 21.

          L2=[ 12  20 14 21] and L1=[22]

  • Go to step 5,  K(1) , K<=|L1|, return selection(L1,K)
  • L1 has only one element 22. return 22.


Related Contents to follow