# Iterative Quick Sort in Java

Problem: - Quick Sort using Iterative approach.

### Sample code for iterative quick sort:

```import java.util.Stack;

public class HeapSortIterative {

static int[] input2 = { 2, 23, 45, 67, 5, 27, 6, 7, 12, 21, 67, 89 };
static int[] input3 = { 2, 23, 45, 67, 5, 27, 6, 7, 12, 21, 67, 89 };

/**
* Sorting of complexity O(nlogn)
*/
public static void main(String[] args) {
System.out.println("\n==========Iterative Quicksort============");
int[] input1 = { 2, 23, 5, 27, 6, 7, 12, 21 };
System.out.println("Before sorting");
for (int i = 0; i < input1.length; i++) {
System.out.print(input1[i] + " ");
}
iterativeQuicksort(input1, 0, input1.length - 1);
System.out.println("\n\nAfter sorting");

for (int i = 0; i < input1.length; i++) {
System.out.print(input1[i] + " ");
}
}
// iterative quick sort
public static void iterativeQuicksort(int[] input, int low, int high) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(low);
stack.push(high);
while (!stack.isEmpty()) {
int h = stack.pop();
int l = stack.pop();
int partionIndex = partition(input, l, h, input[h]);
if (partionIndex - 1 > l) {
stack.push(l);
stack.push(partionIndex - 1);
}
if (partionIndex + 1 < h) {
stack.push(partionIndex + 1);
stack.push(h);
}
}
}

private static int partition(int[] input, int low, int high, int pivot) {
int left = low - 1;
int right = high;
while (true) {
while (input[++left] < pivot && left < right)
;
while (input[--right] > pivot && right > 0)
;
if (left <= right)
Util.swap(left, right, input);
else
break;
}
Util.swap(left, high, input);
return left;
}
}
class Util {
@SuppressWarnings("unused")
public static void swap(int i, int j, int[] arr) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
Sample output:-
C:\java-sample> javac HeapSortIterative.java
C:\java-sample> java HeapSortIterative

==========Iterative Quicksort============
Before sorting
2 23 5 27 6 7 12 21

After sorting
2 5 6 7 12 21 23 27