Find nth largest in an Array

You have an array of numbers; you need to find the nth largest in the array in 0(n) Solution

Conventional Algo to find Max and Second Max : 1. First element becomes max and second MAX 2. For all elements in Array you compare each element with MAX if it's greater than MAX=element; and SECONDMAX=MAX; else if element > SECONDMAX then second=element.

Tournament Principle :
From the above picture we can see that we have found the max in the array. Now we know 9 is MAX but we can't say 7 is SECOND MAX since that would be wrong. Number of Comparison's to find MAX = (n/2) + logn(n) = (n-1) in the above case so the above algo is also optimal for finding MAX ; since conventional algo also takes the same. To find SECOND MAX take the players that were directly defeated by MAX. i.e. 9 DIRECTLY DEFEATED BY MAX = 8, 3, 7 If we play the above tournament among 8, 3, 7 we get 8 as second MAX we for this tournament we needed just 2 comparison's Total comparisons to find MAX and second MAX using tournament principle = (n/2) + log(n) + log(n) = (n-1) + log(n) Now to find kth MAX we can play (k/2) such tournaments since in one tournament we get MAX and second MAX..then exclude them and play the tournament again(k/2) times So total comparisons to find kth MAX using above method = (k/2) ((n-1) + log(n)) However in the conventional algo it would be (k/2 passes of array)(2n comparisons to find MAX and second MAX) = k * n So tournament algo is more optimal eg:: if k = 4 and n = 8 Comparison's by conventional algo = 4 * 8 = 32 Comparison's by Tournament algo = (4/2) ((7) + 3) = 2 * 10 = 20

Conventional Solution2: Using MAX HEAP Build a max heap in O(n) ; Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. So total time complexity = O(k logn) To understand building MAX heap in O(n) check http://en.wikipedia.org/wiki/Binary_heap

Code For 3rd largest

int third_biggest(int *arr, int size)
{
	int first = INT_MIN, second = INT_MIN, third = INT_MIN;
	for(int i=0;i first)
		{
			third = second;
			second = first;
			first = arr[i];
		}
		else if(arr[i] > second)
		{
			third = second;
			second = arr[i];
		}
		else if(arr[i] > third)
		{
			third = arr[i];
		}
	}
	return third;
}