QuickSelect ( A Simple Iterative Implementation ) | CPP program for iterative implementation of QuickSelect ; Standard Lomuto partition function ; Implementation of QuickSelect ; Partition a [ left . . right ] around a pivot and find the position of the pivot ; If pivot itself is the k - th smallest element ; If there are more than k - 1 elements on left of pivot , then k - th smallest must be on left side . ; Else k - th smallest is on right side . ; Driver program to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; int partition ( int arr [ ] , int low , int high ) { int pivot = arr [ high ] ; int i = ( low - 1 ) ; for ( int j = low ; j <= high - 1 ; j ++ ) { if ( arr [ j ] <= pivot ) { i ++ ; swap ( arr [ i ] , arr [ j ] ) ; } } swap ( arr [ i + 1 ] , arr [ high ] ) ; return ( i + 1 ) ; } int kthSmallest ( int a [ ] , int left , int right , int k ) { while ( left <= right ) { int pivotIndex = partition ( a , left , right ) ; if ( pivotIndex == k - 1 ) return a [ pivotIndex ] ; else if ( pivotIndex > k - 1 ) right = pivotIndex - 1 ; else left = pivotIndex + 1 ; } return -1 ; } int main ( ) { int arr [ ] = { 10 , 4 , 5 , 8 , 11 , 6 , 26 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 5 ; cout << " K - th ▁ smallest ▁ element ▁ is ▁ " << kthSmallest ( arr , 0 , n - 1 , k ) ; return 0 ; }