Kth smallest element using quick select algorithm

In the previous article, we learned about the Huffman Coding in Data Structures, In this article, we will learn about the Kth smallest element using quick select algorithm.

236

The selection algorithm is an algorithm for finding the kth smallest/largest number in a list which is also called kth order statistic. This includes finding the minimum, maximum, and median elements. For finding the kth order statistic, there are multiple solutions that provide different complexities and we will have a look at them.

Selection by sorting

A selection problem can be converted into a sorting problem. In this method, we first sort the input elements and then get the desired element. It is efficient if we want to perform many selections.

For example, let us say we want to get the minimum element. After sorting the input elements we can simply return the first element (assuming the array is sorted in ascending order).

Now, if we want to find the second smallest element, we can simply return the second element from the sorted list.

That means, for the second smallest element we are not performing the sorting again. The same is also the case with subsequent queries.

 Even if we want to get k th smallest element, just one scan of the sorted list is enough to find the element (or we can return the k th -indexed value if the elements are in the array).

 From the above discussion what we can say is, with the initial sorting we can answer any query in one scan, O(n).

In general, this method requires O(nlogn) time (for sorting), where n is the length of the input list.

Given below is the code for this algorithm –

#include <bits/stdc++.h>

using namespace std;

int kthSmallest(int arr[], int N, int K)

{

sort(arr, arr + N);

return arr[K - 1];

}

int main()

{

int arr[] = { 12, 3, 5, 7, 19 };

int N = sizeof(arr) / sizeof(arr[0]), K = 2;

 

cout << "K'th smallest element is "

<< kthSmallest(arr, N, K);

return 0;

}

But, this method has a high time complexity of n*logn. So to do this in a better time complexity, a better method is used which uses quick select algorithm.

Kth smallest element using quick select algorithm

As we did in the quick sort algorithm, we used to select a pivot element at bring it to its actual position such that all the elements to the left of it are smaller than it and all the elements right to it are greater than it.

But here, we will check if the element at its correct position is the kth smallest or not.

We will understand it better with the help of an example –

For example, we will consider the array [1,3,2,4,8,5]. And, we have to find the 2nd largest element.

Now, we will take the last element, i.e., 5 as the pivot element. Taking this as the pivot and fixing its position we will get the array as – [1,3,2,4,5,8] where 5 is at 4th index. Which also means that it is the 5th smallest element. Because there are 4 elements smaller than it that is to the left of it.

Similarly, we will repeat the procedure until we will get the kth smallest element.

Now, we will check the code for this algorithm –

#include <bits/stdc++.h>

using namespace std;

int partition(int arr[], int l, int r);

int kthSmallest(int arr[], int l, int r, int K)

{

if (K > 0 && K <= r - l + 1) {

int pos = partition(arr, l, r);
 

if (pos - l == K - 1)

return arr[pos];

if (pos - l > K - 1) // If position is more, recur

return kthSmallest(arr, l, pos - 1, K);

return kthSmallest(arr, pos + 1, r,K - pos + l - 1);

}

return INT_MAX;

}

 
void swap(int* a, int* b)

{

int temp = *a;

*a = *b;

*b = temp;

}

int partition(int arr[], int l, int r)

{

int x = arr[r], i = l;

for (int j = l; j <= r - 1; j++) {

if (arr[j] <= x) {

swap(&arr[i], &arr[j]);

i++;

}

}
 

swap(&arr[i], &arr[r]);

return i;

}

int main()

{

int arr[] = { 12, 3, 5, 7, 4, 19, 26 };

int N = sizeof(arr) / sizeof(arr[0]), K = 3;

cout << "K'th smallest element is "

<< kthSmallest(arr, 0, N - 1, K);

return 0;

}

So, in this article, we learned how to find the kth smallest element. This algorithm is used in a lot of problems of DSA.

Attempt free Data Structures MCQ Test

Previous articleHuffman Coding – Letter Encoding using Huffman Tree
Next articleWhat is Dynamic Programming : Properties & examples
Harshit Brijwasi
I am Harshit Brijwasi. I am an engineer and a Technical Content writer. I am here to share my knowledge about technical topics and help researchers with them.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.