package misc;
import java.util.Arrays;
import java.util.Stack;
public class QuickSort {
/**
* Iterative implementation of QuickSort sorting algorithm.
*
* */
public static void iterativeQuickSort(int[] numbers) {
Stack stack = new Stack<>();
stack.push(0);
stack.push(numbers.length);
while(!stack.isEmpty()) {
int end = (int) stack.pop();
int start = (int) stack.pop();
if(end - start < 2) {
continue;
}
int p = start + ((end - start) / 2);
p = partition(numbers, p, start, end);
stack.push(p + 1);
stack.push(end);
stack.push(start);
stack.push(p);
}
}
/**
* Utility method to partition the array into smaller array, and
* comparing numbers to rearrange them as per QuickSort algorithm.
**/
private static int partition(int[] input, int position, int start, int end) {
int l = start;
int h = end - 2;
int piv = input[position];
swap(input, position, end - 1);
while(l < h) {
if(input[l] < piv) {
l++;
} else if(input[h] >= piv) {
h--;
} else {
swap(input, l, h);
}
}
int idx = h;
if(input[h] < piv) {
idx++;
}
swap(input, end - 1, idx);
return idx;
}
/**
* Utility method to swap two numbers
**/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] array = {34, 32, 43, 12, 11, 32, 22, 21, 32};
System.out.println("Before Sorting: " + Arrays.toString(array));
iterativeQuickSort(array);
System.out.println("After Sorting: " + Arrays.toString(array));
}
}