# Kth smallest element in an array

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

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);
}
}
```