int find_ith_smallest_elem(int* A, int left, int right, int i) { if (left==right) //only one element left, then it's the answer return A[left]; pivot = random_partition(A,left,right); left_partition_length = pivot - left + 1; //1 counts for the pivot itself if (i==left_partition_length) return A[pivot]; //pivot is the answer else if (i<left_partition_length) return find_ith_smallest_elem(A,left,pivot-1,i); else return find_ith_smallest_elem(A,pivot+1,right,i-left_partition_length); } //randomly choose a pivot and partition the array into two parts, where the left part only //contains elements smaller than the pivot while the right part only contains larger ones int random_partition(int* A, int left, int right) { int pivot = rand(left,right); swap(A,pivot,right); // swap the pivot and the right-most element int pivot_value = A[right]; int i = left - 1; for(int j=left; j<right; ++j) { if (A[j]<=pivot_value) { i++; swap(A,i,j); } } swap(A,i+1,right); return i+1; }

## Monday, December 12, 2011

### Find the ith smallest element of the array in O(n)

How to find the ith smallest element of the array in O(n) time is a frequently asked question. The straightforward solution is sorting the array and return the ith element. However, for general cases, it's proven that sorting algorithms like merge sorting, is lower bound to O(nlogn). Thus finding the ith smallest element is unfeasible by a merge sorting. Although for some special cases, such as, the possible values or data range of the array is relatively small, counting sorting can give a O(n) solution, it doesn't work for general cases. The solution below works generally and the expected running time is O(n).

Subscribe to:
Post Comments (Atom)

Coding is thing which is beyond my understanding but still I try to learn it. Going to show this to my friend who is a programmer and learn about it. thanks

ReplyDelete