**Problem Statement** – Given an unsorted array of N elements, find the k^{th} smallest element. k^{th} 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 k^{th} element is the k^{th} 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** –

C

// Quick Select procedure to search for // 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); } }