See Introduction to Algorithms, Second edition , Cormen, Chapter 9 :
Returns the ith smallest element of Array A[p..r] SelectKth(A, p, r, i) { if (p==r) return A[p]; q = Partition(A, p, r); k = q - p + 1; if ( i == k) return A[q]; else if ( i < k ) return SelectKth(A, p, q-1, i) else return SelectKth(A, q+1, r, i - k); }
1 comment:
See Introduction to Algorithms, Second edition , Cormen, Chapter 9 :
Returns the ith smallest element of Array A[p..r]
SelectKth(A, p, r, i)
{
if (p==r) return A[p];
q = Partition(A, p, r);
k = q - p + 1;
if ( i == k)
return A[q];
else if ( i < k )
return SelectKth(A, p, q-1, i)
else
return SelectKth(A, q+1, r, i - k);
}
Post a Comment