package SamsArrays;
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
public void quickSort(int[] arr) {
quickSort(arr, 0, arr.length-1);
}
private void quickSort(int[] arr, int low, int high) {
if(low < high+1) {//if the distance between low and high is greater than 1
//(in other words if there's still more than one item to
//sort in that range of that partition),
int pi = partition(arr,low,high);//then we shall get a new pivot value (see partition function).
//Once we have the pivot, we need to call the quickSort function on both the left and right groups
//(partitions) of the pivot, so we can sort their elements:
quickSort(arr, low, pi-1);//left partition (low = leftmost element, pi-1 = rightmost element)
quickSort(arr, pi+1, high);//right partition (pi+1 = leftmost element, high = rightmost element)
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private int getPivot(int low, int high) {
Random rand = new Random();
return rand.nextInt((high - low) + 1) + low;
}
private int partition(int[] arr, int low, int high) {
swap(arr, low, getPivot(low,high));//Swap the pivot value with the leftmost position (z),
int border = low + 1;//and then create a border value that points to the next right hand element of z.
for(int i = border; i <= high; i++) {
if(arr[i] < arr[low]) {//If the current element is less than the pivot,
swap(arr, i, border++);//then swap it with the border value.
System.out.println("We now have: " + Arrays.toString(arr));
}
}
swap(arr, low, border-1);//After the iteration, swap the pivot value into its proper position,
return border-1;//and return the new index of the pivot value.
}
}