Quick Sort Algorithm

public class QuickSort {
    // Main function to sort array using Quick Sort
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pivotIndex = partition(arr, low, high);
            // Recursively sort elements before and after partition
            quickSort(arr, low, pivotIndex - 1);  // Sort left subarray
            quickSort(arr, pivotIndex + 1, high); // Sort right subarray
        }
    }
    // Partition function - places pivot in correct position
    private static int partition(int[] arr, int low, int high) {
        // Choose the last element as pivot
        int pivot = arr[high];
        // Index of smaller element
        int i = low - 1;
        // Traverse through all elements
        // If current element is smaller than pivot, swap it
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // Swap arr[i] and arr[j]
                swap(arr, i, j);
            }
        }
        // Place pivot in correct position
        swap(arr, i + 1, high);
        return i + 1; // Return pivot index
    }
    // Helper function to swap two elements
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // Helper function to print array
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    // Test the Quick Sort implementation
    public static void main(String[] args) {
        int[] arr = {8, 3, 1, 7, 0, 10, 2};
        System.out.println("Original array:");
        printArray(arr);
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}
/*
 * How it works:
 *
 * Step 1: partition([8,3,1,7,0,10,2], 0, 6)
 *   pivot = 2
 *   After partition: [0,1,2,7,3,10,8]
 *   Return index: 2
 *
 * Step 2: Recursively sort left [0,1] and right [7,3,10,8]
 *
 * Left part: [0,1]
 *   pivot = 1
 *   Already sorted: [0,1]
 *
 * Right part: [7,3,10,8]
 *   pivot = 8
 *   After partition: [7,3,8,10]
 *   Continue recursively...
 *
 * Final result: [0,1,2,3,7,8,10]
 *
 * Time Complexity: O(n log n) average, O(n²) worst case
 * Space Complexity: O(log n) for recursion stack
 */

import java.util.Random;
public class RandomizedQuickSort {
    private static Random random = new Random();
    // Main function with randomized pivot
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Use randomized partition instead of regular partition
            int pivotIndex = randomizedPartition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    // Randomized partition - randomly select pivot
    private static int randomizedPartition(int[] arr, int low, int high) {
        // Generate random index between low and high
        int randomIndex = low + random.nextInt(high - low + 1);
        // Swap random element with last element
        swap(arr, randomIndex, high);
        // Now use regular partition with randomized pivot
        return partition(arr, low, high);
    }
    // Regular partition function (same as before)
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // Test with already sorted array (worst case for regular quick sort)
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println("Original array (sorted):");
        printArray(arr);
        quickSort(arr, 0, arr.length - 1);
        System.out.println("After Quick Sort:");
        printArray(arr);
        System.out.println("\nNote: Randomized pivot helps avoid O(n²) on sorted arrays!");
    }
}
/*
 * Why Randomized Pivot?
 *
 * Problem with regular Quick Sort:
 * - If array is already sorted (or reverse sorted)
 * - And we always pick last element as pivot
 * - We get worst case O(n²) performance!
 *
 * Example: [1,2,3,4,5] with last element pivot
 * - Pivot = 5 → splits into [1,2,3,4] and []
 * - Pivot = 4 → splits into [1,2,3] and []
 * - This creates unbalanced partitions → O(n²)
 *
 * Solution: Random Pivot
 * - Pick random element as pivot
 * - Average case: balanced partitions
 * - Expected time: O(n log n) even on sorted data!
 *
 * Trade-off: Adds randomness overhead, but avoids worst case
 */

public class ThreeWayQuickSort {
    // Three-way Quick Sort - optimized for duplicate keys
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition into three parts: < pivot, = pivot, > pivot
            int[] pivots = threeWayPartition(arr, low, high);
            int lt = pivots[0]; // Last index of elements < pivot
            int gt = pivots[1]; // First index of elements > pivot
            // Recursively sort elements less than and greater than pivot
            // Elements equal to pivot are already in correct position!
            quickSort(arr, low, lt);
            quickSort(arr, gt, high);
        }
    }
    // Three-way partition: returns [lt, gt]
    // lt: last index of elements < pivot
    // gt: first index of elements > pivot
    private static int[] threeWayPartition(int[] arr, int low, int high) {
        int pivot = arr[low]; // Choose first element as pivot
        int lt = low;       // Elements before lt are < pivot
        int i = low + 1;    // Current element being examined
        int gt = high;      // Elements after gt are > pivot
        while (i <= gt) {
            if (arr[i] < pivot) {
                // Element is less than pivot - move to left section
                swap(arr, lt, i);
                lt++;
                i++;
            } else if (arr[i] > pivot) {
                // Element is greater than pivot - move to right section
                swap(arr, i, gt);
                gt--;
                // Don't increment i - need to examine swapped element
            } else {
                // Element equals pivot - leave it in middle
                i++;
            }
        }
        return new int[]{lt - 1, gt + 1};
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // Array with many duplicates
        int[] arr = {4, 2, 7, 2, 4, 1, 7, 4, 2, 7};
        System.out.println("Original array (with duplicates):");
        printArray(arr);
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}
/*
 * Three-Way Partitioning Visualization:
 *
 * Array: [4, 2, 7, 2, 4, 1, 7, 4, 2, 7]
 * Pivot: 4 (first element)
 *
 * After partition:
 * [2, 2, 1, 2] [4, 4, 4] [7, 7, 7]
 *  < pivot      = pivot    > pivot
 *
 * Advantages for duplicate keys:
 * 1. Elements equal to pivot don't need further sorting
 * 2. Reduces number of recursive calls
 * 3. Much faster than regular Quick Sort for arrays with duplicates
 *
 * Example use case:
 * - Sorting colors: [Red, Blue, Red, Green, Blue, Red, Green]
 * - All Reds grouped together after one partition!
 *
 * Time Complexity:
 * - Best/Average: O(n log n)
 * - Worst: O(n²) but rare
 * - Optimal: O(n) when all elements are equal!
 */