import java.util.Arrays;
public class QuickSort {
// Lomuto partition scheme — pivot = last element
static int partitionLomuto(int[] arr, int low, int high) {
int pivot = arr[high]; // choose last element as pivot
int i = low - 1; // index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
// Place pivot in correct position
int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
return i + 1; // pivot index
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partitionLomuto(arr, low, high);
quickSort(arr, low, pi - 1); // sort left of pivot
quickSort(arr, pi + 1, high); // sort right of pivot
}
}
// Hoare partition scheme — more efficient (fewer swaps)
static int partitionHoare(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("Before: " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("After: " + Arrays.toString(arr));
// After: [1, 5, 7, 8, 9, 10]
}
}
/*
* Partition trace for [10, 7, 8, 9, 1, 5], pivot=5:
* i=-1, j=0: arr[0]=10 > 5, skip
* j=1: arr[1]=7 > 5, skip
* j=2: arr[2]=8 > 5, skip
* j=3: arr[3]=9 > 5, skip
* j=4: arr[4]=1 <= 5, i=0, swap arr[0] and arr[4] → [1,7,8,9,10,5]
* Place pivot: swap arr[1] and arr[5] → [1,5,8,9,10,7]
* pivot index = 1
*/
import java.util.Arrays;
import java.util.Random;
public class RandomizedQuickSort {
static Random rand = new Random();
// Randomized pivot — avoids O(n²) worst case on sorted input
static int randomPartition(int[] arr, int low, int high) {
int randomIdx = low + rand.nextInt(high - low + 1);
// Swap random element with last element
int temp = arr[randomIdx]; arr[randomIdx] = arr[high]; arr[high] = temp;
// Now use standard Lomuto partition
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
return i + 1;
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
// [1, 1, 2, 3, 6, 8, 10]
}
}
/*
* Randomized Quick Sort:
* - Expected O(n log n) for ALL inputs
* - Eliminates worst case for sorted/reverse-sorted arrays
* - Used in practice (Java's Arrays.sort for primitives uses dual-pivot quicksort)
*/