Iterative Quick Sort | Function takes last element as pivot , places the pivot element at its correct position in sorted array , and places all smaller ( smaller than pivot ) to left of pivot and all greater elements to right of pivot ; The main function that implements QuickSort arr [ ] -- > Array to be sorted , low -- > Starting index , high -- > Ending index Function to do Quick sort ; pi is partitioning index , arr [ p ] is now at right place ; Driver Code
def partition ( arr , low , high ) : NEW_LINE INDENT i = ( low - 1 ) NEW_LINE pivot = arr [ high ] 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 quickSort ( arr , low , high ) : NEW_LINE INDENT if low < high : NEW_LINE INDENT pi = partition ( arr , low , high ) NEW_LINE quickSort ( arr , low , pi - 1 ) NEW_LINE quickSort ( arr , pi + 1 , high ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , 2 , 6 , 9 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE quickSort ( arr , 0 , n - 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT