public class QuickSort {
public static void main(String[] args) {
int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
System.out.println("Before: " + Arrays.toString(array));
sort1(array);
System.out.println("After: " + Arrays.toString(array));
array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
sort2(array);
System.out.println("After: " + Arrays.toString(array));
array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
sort3(array);
System.out.println("After: " + Arrays.toString(array));
}
public static void sort1(int[] arr) {
recurse(arr, 0, arr.length - 1);
}
private static void recurse(int[] arr, int low, int high) {
if (arr.length <= 0) {
return;
}
if (low >= high) return;
int left = low;
int right = high;
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
recurse(arr, low, left - 1);
recurse(arr, left + 1, high);
}
public static void sort2(int[] arr) {
if (arr.length <= 0) {
return;
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(arr.length - 1);
while (!stack.isEmpty()) {
int high = stack.pop();
int low = stack.pop();
int pivotIdx = partition(arr, low, high);
if (pivotIdx > low) {
stack.push(low);
stack.push(pivotIdx - 1);
}
if (pivotIdx < high && pivotIdx >= 0) {
stack.push(pivotIdx + 1);
stack.push(high);
}
}
}
public static void sort3(int[] arr) {
if (arr.length <= 0) {
return;
}
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
queue.offer(arr.length - 1);
while (!queue.isEmpty()) {
int low = queue.poll();
int high = queue.poll();
int pivotIdx = partition(arr, low, high);
if (pivotIdx > low) {
queue.offer(low);
queue.offer(pivotIdx - 1);
}
if (pivotIdx < high && pivotIdx >= 0) {
queue.offer(pivotIdx + 1);
queue.offer(high);
}
}
}
private static int partition(int[] arr, int low, int high) {
if (arr.length <= 0) {
return -1;
}
if (low >= high) {
return -1;
}
int left = low;
int right = high;
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
}