# kth largest element in array in c

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

## Leave a Reply