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));
	}
}