Iterative Quick Sort | This function is same in both iterative and recursive ; Function to do Quick sort arr [ ] -- > Array to be sorted , l -- > Starting index , h -- > Ending index ; Create an auxiliary stack ; initialize top of stack ; push initial values of l and h to stack ; Keep popping from stack while is not empty ; Pop h and l ; Set pivot element at its correct position in sorted array ; If there are elements on left side of pivot , then push left side to stack ; If there are elements on right side of pivot , then push right side to stack ; Driver code to test above ; Function calling
def partition ( arr , l , h ) : NEW_LINE INDENT i = ( l - 1 ) NEW_LINE x = arr [ h ] NEW_LINE for j in range ( l , h ) : NEW_LINE INDENT if arr [ j ] <= x : NEW_LINE INDENT i = i + 1 NEW_LINE arr [ i ] , arr [ j ] = arr [ j ] , arr [ i ] NEW_LINE DEDENT DEDENT arr [ i + 1 ] , arr [ h ] = arr [ h ] , arr [ i + 1 ] NEW_LINE return ( i + 1 ) NEW_LINE DEDENT def quickSortIterative ( arr , l , h ) : NEW_LINE INDENT size = h - l + 1 NEW_LINE stack = [ 0 ] * ( size ) NEW_LINE top = - 1 NEW_LINE top = top + 1 NEW_LINE stack [ top ] = l NEW_LINE top = top + 1 NEW_LINE stack [ top ] = h NEW_LINE while top >= 0 : NEW_LINE INDENT h = stack [ top ] NEW_LINE top = top - 1 NEW_LINE l = stack [ top ] NEW_LINE top = top - 1 NEW_LINE p = partition ( arr , l , h ) NEW_LINE if p - 1 > l : NEW_LINE INDENT top = top + 1 NEW_LINE stack [ top ] = l NEW_LINE top = top + 1 NEW_LINE stack [ top ] = p - 1 NEW_LINE DEDENT if p + 1 < h : NEW_LINE INDENT top = top + 1 NEW_LINE stack [ top ] = p + 1 NEW_LINE top = top + 1 NEW_LINE stack [ top ] = h NEW_LINE DEDENT DEDENT DEDENT arr = [ 4 , 3 , 5 , 2 , 1 , 3 , 2 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE quickSortIterative ( arr , 0 , n - 1 ) NEW_LINE print ( " Sorted ▁ array ▁ is : " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( " % ▁ d " % arr [ i ] ) , NEW_LINE DEDENT