Program for Iterative Quick Sort in Java
Below is the implementation of Iterative Quick Sort:
Java
// Java implementation of iterative quick sort import java.io.*; public class IterativeQuickSort { void swap( int arr[], int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } /* This function is same in both iterative and recursive*/ int partition( int arr[], int l, int h) { int x = arr[h]; int i = (l - 1 ); for ( int j = l; j <= h - 1 ; j++) { if (arr[j] <= x) { i++; // swap arr[i] and arr[j] swap(arr, i, j); } } // swap arr[i+1] and arr[h] swap(arr, i + 1 , h); return (i + 1 ); } // Sorts arr[l..h] using iterative QuickSort void QuickSort( int arr[], int l, int h) { // create auxiliary stack int stack[] = new int [h - l + 1 ]; // initialize top of stack int top = - 1 ; // push initial values in the stack stack[++top] = l; stack[++top] = h; // keep popping elements until stack is not empty while (top >= 0 ) { // pop h and l h = stack[top--]; l = stack[top--]; // set pivot element at it's proper position int p = partition(arr, l, h); // If there are elements on left side of pivot, // then push left side to stack if (p - 1 > l) { stack[++top] = l; stack[++top] = p - 1 ; } // If there are elements on right side of pivot, // then push right side to stack if (p + 1 < h) { stack[++top] = p + 1 ; stack[++top] = h; } } } // A utility function to print contents of arr void printArr( int arr[], int n) { int i; for (i = 0 ; i < n; ++i) System.out.print(arr[i] + " " ); } // Driver code to test above public static void main(String args[]) { IterativeQuickSort ob = new IterativeQuickSort(); int arr[] = { 4 , 3 , 5 , 2 , 1 , 3 , 2 , 3 }; ob.QuickSort(arr, 0 , arr.length - 1 ); ob.printArr(arr, arr.length); } } |
Output
1 2 2 3 3 3 4 5
Complexity of the above method:
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
About Iterative Quick Sort
Optimizations for recursive quick sort can also be applied to the iterative version.
- Partition process is the same in both recursive and iterative. The same techniques to choose the optimal pivot can also be applied to the iterative version.
- To reduce the stack size, first, push the indexes of the smaller half.
- Use insertion sort when the size reduces below an experimentally calculated threshold.
Reference: Please refer complete article on Iterative Quick Sort for more details!
Java Program for Iterative Quick Sort
In this article, we will learn about Iterative Quick Sort.
Contact Us