Iterative Quick Sort | A utility function to swap two elements ; This function is same in both iterative and recursive ; A [ ] -- > 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 ; A utility function to print contents of arr ; Driver code ; Function calling
< ? php function swap ( & $ a , & $ b ) { $ t = $ a ; $ a = $ b ; $ b = $ t ; } function partition ( & $ arr , $ l , $ h ) { $ x = $ arr [ $ h ] ; $ i = ( $ l - 1 ) ; for ( $ j = $ l ; $ j <= $ h - 1 ; $ j ++ ) { if ( $ arr [ $ j ] <= $ x ) { $ i ++ ; swap ( $ arr [ $ i ] , $ arr [ $ j ] ) ; } } swap ( $ arr [ $ i + 1 ] , $ arr [ $ h ] ) ; return ( $ i + 1 ) ; } function quickSortIterative ( & $ arr , $ l , $ h ) { $ stack = array_fill ( 0 , $ h - $ l + 1 , 0 ) ; $ top = -1 ; $ stack [ ++ $ top ] = $ l ; $ stack [ ++ $ top ] = $ h ; while ( $ top >= 0 ) { $ h = $ stack [ $ top -- ] ; $ l = $ stack [ $ top -- ] ; $ p = partition ( $ arr , $ l , $ h ) ; if ( $ p - 1 > $ l ) { $ stack [ ++ $ top ] = $ l ; $ stack [ ++ $ top ] = $ p - 1 ; } if ( $ p + 1 < $ h ) { $ stack [ ++ $ top ] = $ p + 1 ; $ stack [ ++ $ top ] = $ h ; } } } function printArr ( $ arr , $ n ) { for ( $ i = 0 ; $ i < $ n ; ++ $ i ) echo $ arr [ $ i ] . " ▁ " ; } $ arr = array ( 4 , 3 , 5 , 2 , 1 , 3 , 2 , 3 ) ; $ n = count ( $ arr ) ; quickSortIterative ( $ arr , 0 , $ n - 1 ) ; printArr ( $ arr , $ n ) ; ? >