import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 1, 10, 5, 3, 6 };
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] array) {
quickSortUtil(array, 0, array.length - 1);
}
private static void quickSortUtil(int[] array, int startIdx, int endIdx) {
if (startIdx >= endIdx) {
return;
}
int pivotIdx = startIdx;
int leftIdx = startIdx + 1;
int rightIdx = endIdx;
while (leftIdx <= rightIdx) {
if (array[leftIdx] > array[pivotIdx] && array[rightIdx] < array[pivotIdx]) {
swap(leftIdx, rightIdx, array);
}
if (array[leftIdx] <= array[pivotIdx]) {
leftIdx++;
}
if (array[rightIdx] >= array[pivotIdx]) {
rightIdx--;
}
}
swap(pivotIdx, rightIdx, array);
quickSortUtil(array, startIdx, rightIdx - 1);
quickSortUtil(array, rightIdx + 1, endIdx);
}
private static void swap(int i, int j, int[] array) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}