Iterative Quick Sort | Java program for implementation of QuickSort ; This 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 ; 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 ; Driver code ; Function calling
import java . util . * ; class QuickSort { static 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 ++ ; int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; } } int temp = arr [ i + 1 ] ; arr [ i + 1 ] = arr [ high ] ; arr [ high ] = temp ; return i + 1 ; } static void quickSortIterative ( int arr [ ] , int l , int h ) { int [ ] stack = new int [ h - l + 1 ] ; int top = - 1 ; stack [ ++ top ] = l ; stack [ ++ top ] = h ; while ( top >= 0 ) { h = stack [ top -- ] ; l = stack [ top -- ] ; int 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 ; } } } public static void main ( String args [ ] ) { int arr [ ] = { 4 , 3 , 5 , 2 , 1 , 3 , 2 , 3 } ; int n = 8 ; quickSortIterative ( arr , 0 , n - 1 ) ; for ( int i = 0 ; i < n ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } } }