QuickSelect ( A Simple Iterative Implementation ) | 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 Code
def partition ( arr , low , high ) : NEW_LINE INDENT pivot = arr [ high ] NEW_LINE i = ( low - 1 ) NEW_LINE for j in range ( low , high ) : NEW_LINE INDENT if arr [ j ] <= pivot : NEW_LINE INDENT i += 1 NEW_LINE arr [ i ] , arr [ j ] = arr [ j ] , arr [ i ] NEW_LINE DEDENT DEDENT arr [ i + 1 ] , arr [ high ] = arr [ high ] , arr [ i + 1 ] NEW_LINE return ( i + 1 ) NEW_LINE DEDENT def kthSmallest ( a , left , right , k ) : NEW_LINE INDENT while left <= right : NEW_LINE INDENT pivotIndex = partition ( a , left , right ) NEW_LINE if pivotIndex == k - 1 : NEW_LINE INDENT return a [ pivotIndex ] NEW_LINE DEDENT elif pivotIndex > k - 1 : NEW_LINE INDENT right = pivotIndex - 1 NEW_LINE DEDENT else : NEW_LINE INDENT left = pivotIndex + 1 NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT arr = [ 10 , 4 , 5 , 8 , 11 , 6 , 26 ] NEW_LINE n = len ( arr ) NEW_LINE k = 5 NEW_LINE print ( " K - th ▁ smallest ▁ element ▁ is " , kthSmallest ( arr , 0 , n - 1 , k ) ) NEW_LINE