Find Kth smallest element in array

Kth smallest element in array

Given an set of numbers in non-sorted order, find the Kth smallest element in an array.Kth smallest element means there are N-K-1 elements in set which are greater than the desired element.

We can solve this problem in two simple steps:
1. Sort the input set.
2. Scan the array till Kth element, it gives us the Kth smallest element in array

Thing to ponder upon here is can we do better? Can we avoid the second step? Can we reduce the size of input to be sorted or not sorting the input at all? Answer to all above questions is Yes. Think Quick sort.

Algorithm to find Kth smallest element

Quick sort does not completely sorts two sub arrays when it gives us the correct position of pivot.By property of quick sort we know that all elements which are on left side of pivot are less than pivot.

Let’s say we have pivot swapped with jth element of the input set, so there are j elements which are less than pivot. Can we use this information to find Kth smallest element? Absolutely yes.
If j is less than K, then we have smaller left subset and we need to look into right subset of the input to get the Kth smallest element. So we look (K-j)th smallest element in the right subset.
Here we have not sorted left or right subset of the input and still we reduced the candidate by almost half.
If j is more than K, then we need to look in left subset of input. Here we have discarded the right subset of the input.
As we are doing partitions and calculating the position of pivot, we don’t need to scan the array afterwards. As soon as position of pivot is equal to K, we got element.

Let’s say we have an array with following elements 4,2,1,7,5,3,8,10,9,6 and we need to find fifth smallest element in this array. In this example output will be 5.
kth smallest element in array

We have pivot as 1st element i.e 4 and we divide the remaining array in such a way that we find the correct position of 4.

Once 4 is in correct position, all the elements on left side are less than pivot i.e 4 and on right side, are greater than pivot.
Now check the position of pivot, if it is K-1 (array is represented as zero base index), then pivot is our element.
Here final position of 4 after first execution of quick sort function will be index 3.
kth smallest element in array example

Since pivot position is less than K-1 i.e 4, we need to look for element in right side of the pivot. Notice that we are not reducing K as pivot position is given w.r.t whole array and not w.r.t sub-array under consideration.

In second iteration, 5 will be pivot. After second execution of quick sort array will look as below

Pivot index is now 4 which is equal to K-1. Hence our 5th smallest element in this array is 5. Note that we have not sorted the complete array.

Kth smallest element in array implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

void swap(int *a, int *b){

    int temp = *a;
    *a = *b;
    *b = temp;

}
int partition(int A[], int start, int end){
    int i= start+1;
    int j = i;
    int pivot = start;
    for(; i<end; i++){
        if(A[i]<A[pivot]){
            swap(&A[i],&A[j]);
            j++;
        }
    }
    if(j<=end){
        swap(&A[pivot],&A[j-1]);
    }
    for(i=0;i<10;i++){
        printf("%d  ", A[i] );
    }
    printf("\n");
        return j-1;
}

void quick_sort(int A[], int start, int end, int K){
    int part ;
    if(start <end) {
        part  =  partition(A, start, end);
            if(part == K-1){
                printf("kth smallest element : %d" , A[part]);
            }
        if(part>K-1){
            quick_sort(A, start,part, K);
        }
        else{
            quick_sort(A, part+1, end, K);
        }
    }
    return;
}

/* Driver program for the function written above */
int main(){
    int array[] = {4,2,1,7,5,3,8,10,9,6};
    int n = sizeof(array)/sizeof(array[0]);
    quick_sort(array,0, n, 4);
    return 0;
}

As we are reducing the candidates by half, our equation of complexity becomes :  T(n)  = T(n/2) + T(n/2)

If we directly take Master theorem, complexity becomes O(nlogn).
There is a catch here, if input is in sorted order, then worst case complexity becomes O(n2), So we can first scan input and if it is sorted, we can simply count the elements and find out the Kth smallest element. Please refer to previous quicksort algorithm for details how we can select pivot so that quick sort does not go for worst case performance irrespective of the nature and order of input.

Finding Kth smallest element is typical application of quick sort. We can apply quick sort algorithm in any problem where we need to find out relative position of an element w.r.t others without actually sorting the elements of input.

Please share if there is something wrong or missing, If you want to contribute to algorithms and me, please contact us.

  • Ankit Gupta

    Suppose an array contains -1,2,5,3,2,6. If we find out the 3rd smallest number the algo above will give 2 which is not. Answer should be 3. Anyway to handle duplicate situation

    • http://algorithmsandme.in/ Jitendra Sangar

      Hi Ankit,
      If we have duplicates in array, better we go for min heap implementation and not for quick sort approach. I have written a post on that too, just search for heaps on this blog and you will get that.
      Thanks
      Sangar Jitendra

    • Ankit Gupta

      Thank you. I will look into it.

  • david

    what would I need to do to be able to include negative values in the array?

    • http://algorithmsandme.in/ Jitendra Sangar

      There is nothing special that needs to be done for negative value.
      Just change the input and check at : http://ideone.com/gsyNm6

  • Pingback: Find Kth smallest element in binary search tree - Algorithms and Me()

  • Pingback: Find Kth smallest element in two sorted arrays - Algorithms and Me()