package com.exuan.qsort;
//Time complexity
//average:O(N)
//best:O(NlogN)
//worst:O(N2)
public class QSort {
public static void main(String[] args)
{
int[] data = {12,13,13,14,8,2,11,5,4,6,7,3,1,9,10,17,0};
display(data);
quickSort(data, 0, data.length -1);
display(data);
}
/*quick sort the data from index x to index y
* 1.appoint a pivot value(here the first index of data)
* 2.find the first value which is less than the pivot from right to left, swap it with the pivot
* 3.find the first value which is greater than the pivot from left to right, swap it with the pivot
* Then after one round of quick sort, data will divided into two parts,
* data left of pivot is less than pivot while data right of pivot is greater than key,
* Note that we don't really need to do the swap, because the pivot always changes
* recursive call quick sort
*/
private static void quickSort(int[] data, int x, int y)
{
if(x >= y)
{
return;
}
int low = x;
int high = y;
int pivot = data[low];//pick a pivot value
//one round of quick sort, data will divided into two parts
while(low < high)
{
//find the first value which is less than the pivot from right to left
while(low < high && data[high] >= pivot)
{
high--;
}
data[low] = data[high];//swap it with the pivot
//find the first value which is greater than the pivot from left to right
while(low < high && data[low] <= pivot)
{
low++;
}
data[high] = data[low];//swap it with the pivot
}
data[high] = pivot;//here we complete the real swap to assign the pivot
//recursive call quick sort to sort the two parts
quickSort(data, x, low - 1);
quickSort(data, high + 1, y);
}
private static void display(int[] data)
{
for(int i = 0; i < data.length; i++)
{
System.out.print(data[i] + ",");
}
System.out.println();
}
}