Problem Statement – Given an unsorted array of N elements, find the kth smallest element. kth smallest element is the element at index k if the array were sorted.
Clues –
- Solution should be O(N) in time and O(1) in space.
- Can you think of a divide-and-conquer based solution?
- Can you apply Quicksort’s partitioning logic here?
Solution – This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a very useful divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array. A step-by-step version of Quickselect is –
- Calculate the middle element for the given range.
- Place all the elements greater than the mid element to its right.
- Place all the elements lesser than the mid element to its left.
- If ‘k’ is less than the index of the middle element, then recursively call Quickselect on the left half of the range.
- If ‘k’ is greater than the index of the middle element, then recursively call Quickselect on the right half of the range.
Code –
// the kth smallest element in O(N) time.
void quickSelect(int arr[], int low, int high, int k)
{
if (high – low < k) {
// A single element is
// considered to be sorted
return;
}
int mid = low + ((high – low) / 2);
// Put the pivot at the last
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
int pivot = arr[high];
int i = low;
int j = high – 1;
// The partition
while (j >= i) {
if (arr[j] < pivot && arr[i] > pivot) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
++i;
–j;
} else if (arr[j] < pivot && arr[i] <= pivot) {
++i;
} else if (arr[j] >= pivot && arr[i] > pivot) {
–j;
} else if (arr[j] >= pivot && arr[i] <= pivot) {
++i;
–j;
}
}
// Bring the pivot back to its
// appropriate place
temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
if (k >= i) {
quickSelect(arr, i + 1, high, k);
} else {
quickSelect(arr, low, i, k);
}
}
[/code]