import java.util.Arrays;
public class QuickSort {
public static int[] arr = {3, 2, 4, 1, 6, 8, 0};
/*
* 3, 2, 4, 1, 6, 8, 0
* * .
* 3, 2, 0, 1, 6, 8, 4
* . *
* 1, 2, 0, 3, 6, 8, 4
* 1, 2, 0
* * .
* 1, 0, 2
* . *
* 0, 1, 2
* 6, 8, 4
* * .
* 6, 4, 8
* . *
* 4, 6, 8
* 0, 1, 2, 3, 4, 6, 8
*
* average 1.39NlogN
* worst N-square/2 --- shuffle
*/
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
private static int partition(int[] a, int lo, int hi) {
int v = a[lo];
int i = lo;
int j = hi + 1;
while(true){
while(a[++i] <= v) if(i == hi) break;
while(a[--j] >= v) if(j == lo) break;
if(i >= j) break;
swap(a, i, j);
}
swap(a, lo, j);
return j;
}
private static void sort(int[] a, int lo, int hi) {
if(lo >= hi) return;
int j = partition(a, lo, hi);
sort(a, lo, j -1);
sort(a, j + 1, hi);
}
public static int[] sort(int[] a) {
sort(a, 0, a.length - 1);
return a;
}
public static void main(String[] args) {
Arrays.stream(sort(arr)).forEach(System.out::println);
}
}
