Table of Contents

This article finds the kth smallest element in an array by partitioning it.

Consider the following example.

Array= 33, 1, 0, 15, 16, 12, 14, 11, 9, 8, 2 3rd smallest element = 2 5th smallest element = 9

## Naïve Approach

One approach to solving that problem would be to sort the array first, let’s say, using the quick sort algorithm, and then access the element at index `(k-1)`

. Here, we assume that the array starts from index 0. This approach might be intuitive and straightforward. However, its average time complexity is `O(nlogn)`

, where n is the array size. We can find solutions that have better complexities.

## Quick Select Algorithm

As we only want the kth smallest element, there is no need to sort the entire array. The quick select algorithm takes advantage of this idea. Let’s see how it works.

- First, it finds a random pivot element from the array.
- Then, it partitions the array based on that pivot point. Values that are less than the pivot element get shifted to the left, and items greater than that get shifted to the right.
- If the index of the pivot is less than (k-1), then it means our required element lies on the right side of the array. So, only that part gets considered for the next call of the algorithm, i.e., the next pivot will be from this side.
- If the pivot’s position is more than (k-1), then only the left part gets considered.
- If our required (kth smallest) element is equal to the pivot element, then the recursion stops, and that value gets returned.

The algorithm runs until the pivot position is equal to (k-1).

As you can observe, this algorithm works like quicksort. However, it recurs for one side only. Therefore, its average time complexity is better than the quick sort algorithm, i.e., `O(n)`

. The worst-case complexity is still `O(n2)`

.

## Implementation

Consider the following code to find the kth smallest element.

import math import random def partition(array, l, r, index): pivot = array[index] #find the pivot element left=[] #elements less than or equal to pivot right=[] #elements greater than pivot for i in range(l, r+1): if i==index: #leave the pivot element pass elif array[i] <= pivot: left.append(array[i]) else: right.append(array[i]) #make changes in the actual array end_left = l + len(left) array[l: end_left] = left array[end_left] = pivot array[end_left+1:r+1] = right return end_left def selectPivot(array, l, r): #find a random pivot index return random.randint(l, r) def quickSelect(array, l, r, k): if l <= r: index = selectPivot(array, l, r) #get the index of the pivot point pivot_pos = partition(array,l, r, index) #partition the array based on the pivot if pivot_pos==k: #if pivot is the required smallest element then return it return array[k] elif pivot_pos < k: #consider the right part return quickSelect(array,pivot_pos+1, r, k) else: return quickSelect(array, l, pivot_pos-1, k) #consider the left part array=[34, 1, 4, 2, 18, 29, 14, 28, 23] k=3 kth_smallest = quickSelect(array, 0, len(array)-1, k-1) print(f"{k} smallest element is: {kth_smallest}") k=4 kth_smallest = quickSelect(array, 0, len(array)-1, k-1) print(f"{k} smallest element is: {kth_smallest}")

**Output**

3 smallest element is: 4

4 smallest element is: 14

Since we are choosing a random point, we can get unlucky as well. Let’s explain this using an example. We have an array A = [0, 5, 3, 1, 4], and we want to find the 1st smallest element. At first, we get 5 as a pivot. The partitioned array is now [0, 3, 1, 4] as all the elements fall to the left. Next time, we get 4, and then the partitioned array will be [0, 3, 1]. After that, we get 3, 1, and 0 as pivot elements. As you can observe, the algorithm runs 5+4+3+2+1 times or n+n-1+…+1 times, which becomes `O(n2)`

.

## Median of Medians Algorithm

Selecting a pivot in such a way that never leads to the above-given situation can guarantee a time complexity of `O(n)`

in the worst-case scenario as well. For this, we have the median of medians algorithm.

This algorithm works as follows:

- It divides an array into chunks, which are usually of size 5. The last element can have less than 5 items.
- Then, it finds medians of these chunks by sorting and store results in an array.
- If only one median is left, then it gets returned as a pivot element. Otherwise, the algorithm works again on the medians array until we get a single median.

**Code**

Let’s find the kth smallest element using the median of medians method.

import math import random def partition(array, l, r, pivot): index = array.index(pivot) left=[] #elements less than or equal to pivot right=[] #elements greater than pivot for i in range(l, r+1): if i==index: #leave the pivot element pass elif array[i] <= pivot: left.append(array[i]) else: right.append(array[i]) #make changes in the actual array end_left = l + len(left) array[l: end_left] = left array[end_left] = pivot array[end_left+1:r+1] = right return end_left def medianOfMedians(arr, l, r): groups=[] #create chunks of size 5 temp = arr[l:r+1] for i in range(0, len(temp), 5): groups.append(temp[i:i+5]) medians =[] #find median of every chunk for group in groups: medians.append(sorted(group)[(len(group))//2]) l_med = len(medians) if l_med == 1: return medians[0] else: return medianOfMedians(medians, 0, l_med-1) def quickSelect(array, l, r, k): if l <= r: pivot = medianOfMedians(array, l, r) #get the index of the pivot point pivot_pos = partition(array,l, r, pivot) #partition the array based on the pivot if pivot_pos==k: #if pivot is the required smallest element then return it return array[k] elif pivot_pos < k: #consider the right part return quickSelect(array,pivot_pos+1, r, k) else: return quickSelect(array, l, pivot_pos-1, k) #consider the left part arr=[34, 1, 4, 2, 18, 29, 14, 28, 23] k=3 kth_smallest = quickSelect(arr, 0, len(arr)-1, k-1) print(f"{k} smallest element is: {kth_smallest}") k=4 kth_smallest = quickSelect(arr, 0, len(arr)-1, k-1) print(f"{k} smallest element is: {kth_smallest}")

**Output**

3 smallest element is: 4

4 smallest element is: 14

Blog Hero