Quickselect Algorithm | CPP program for implementation of QuickSelect ; Standard partition process of QuickSort ( ) . It considers the last element as pivot and moves all smaller element to left of it and greater elements to right ; This function returns k 'th smallest element in arr[l..r] using QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT ; If k is smaller than number of elements in array ; Partition the array around last element and get position of pivot element in sorted array ; If position is same as k ; If position is more , recur for left subarray ; Else recur for right subarray ; If k is more than number of elements in array ; Driver program to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 kthSmallest ( int arr [ ] , int l , int r , int k ) { if ( k > 0 && k <= r - l + 1 ) { int index = partition ( arr , l , r ) ; if ( index - l == k - 1 ) return arr [ index ] ; if ( index - l > k - 1 ) return kthSmallest ( arr , l , index - 1 , k ) ; return kthSmallest ( arr , index + 1 , r , k - index + l - 1 ) ; } return INT_MAX ; } int main ( ) { int arr [ ] = { 10 , 4 , 5 , 8 , 6 , 11 , 26 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 3 ; cout << " K - th ▁ smallest ▁ element ▁ is ▁ " << kthSmallest ( arr , 0 , n - 1 , k ) ; return 0 ; }