CareerCup

this is a C++ concept - that states point to member - n->0 translates to n to member functions(m).

use a selection algorthm with :

function select(list[1..n], k)
for i from 1 to k
minIndex = i
minValue = list[i]
for j from i+1 to n
if list[j] < minValue
minIndex = j
minValue = list[j]
swap list[i] and list[minIndex]
return list[k]

Heapify the array in O(m) as a max heap and then remove n elements from the heap in O(nlogm).

Overall complexity: O(m + nlogm) which will be almost linear as n->0.

Take an array N of size 'n'. For each element in array, compare with elements in N and make sure that N always has the max three elements.

Finally find the smallest number in N. This will be O(m) coz n is much lesser than m.

int N=5

For[i=0;i<N-1;i++]
{
For[j=1,K=0;j<N-1,K<3;j++]
{
If( A[i]<A[j] && ( (A[j] < B[K]) || K=0 ) )
{
B[K]=A[j]
}
}
K++;
}

Console.writeline(B[K])

run partial quicksort. at each level check if m is less than the no of elements on the left partion. if so execute quick sort on the left else on the right with m = m - no of elements on right. if final pivot index == m return value in m. This is linear on an average case.

But the question says "without sorting".
How about making a bin search tree out of elements and then searching it?

how about a binary min-heap(BMH), similar to ~amv's suggestion.
But no need to heapify the whole array of m elements.
Only keep the n largest sorted.

FOR (list[i=0...m]) { # O(m)
IF ( i <= n )
THEN
insertToBMH(list[i], BMH) # O(log n)
ELSE
min = minValue(BMH) # O(1), just get the root
IF ( list[i] > min )
swap(list[i], BMH-root) # O(1)
heapfiyDown(BMH) # O(log n), bubble-down list[i] from root
END-IF
END-IF
END-FOR

nth-largest = getRoot(BMH) # O(1)

Overall, O(m * 2 * log n)) = O(m log n)

this is discussed in cormen

have a look at section 9.3
worst case O(n)

Given: m elements in the array, n<<m
To Find: n th smallest element

Sol: allocate an array of n elements
as you traverse the list of m elements, compare each of the element with n elements in the array
you'll end up with n smallest of m
Complexity: O(log n)*O(m) => O(m) since n<<m

This is called a Selection Algorithm. Please check for the explanation in wikipedia.

i agree its a selection algorithm. perform selection algorithm till m-n steps.

for small n << m select algorithm is useful

private static int quickSelect(int[] a,int p,int r, int i)
	{
		if(p==r) return p;
		int q=randomizedPartition(a, p, r);
		int k=q-p+1;
		if(i==k)
			return q;
		else if(i<k)
			return quickSelect(a, p, q-1, i);
		else
			return quickSelect(a, q+1, r, i-k);
	}

in array if space complexity doesnt matter the u can do it by making the binarey seach tree of n numbers and finding the kth largest number by just doint the Inorder Traversal :)
but if it also mattrers and u can not rearrange the array it is sure to have that solution will take O(n2) at worse case
if it is right to rearrange the order of elemnts then u can only able tio solve this problem in O(n) solution :)