# Algorithm to return kth largest number

By: indushree-kumar on Jul 24th, 2012  |  syntax: None  |  size: 0.71 KB  |  hits: 14  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. kthLargest(A, k)
2.   let r be a random number in the range 1 to length(A)
3.   let num = A[r]
4.   let A1, A2 be new arrays
5.   /*split the given numbers into a array A1 of small numbers and A2 of big numbers*/
6.   for i = 1 to n
7.     if A[i] < k then
8.       append A[i] to A1
9.     else if A[i] > k then
10.       append A[i] to A2
11.   end for
12.   if k <= length(A1):
13.     /*it's in the pile of small elements*/
14.     return kthLargest(A1, k) /*recursively call kthLargest*/
15.   else if k > length(A) - length(A2)
16.     /*it's in the pile of big elements*/
17.     return kthLargest(A2, k - (length(A) - length(A2))  /*recursively call kthLargest*/
18.   else
19.     /*it's equal to the num*/
20.     return num
21.
22. The complexity of this algorithm is O(n).