Add Randomized Quick Sort (#6234)

VibhuKhera123 · web-flow · commit b09766ede447 · 2025-05-09T21:50:09.000Z
diff --git a/src/main/java/com/thealgorithms/randomized/RandomizedQuickSort.java b/src/main/java/com/thealgorithms/randomized/RandomizedQuickSort.java
@@ -0,0 +1,68 @@
+package com.thealgorithms.randomized;
+
+/**
+ * This class implements the Randomized QuickSort algorithm.
+ * It selects a pivot randomly to improve performance on sorted or nearly sorted data.
+ * @author Vibhu Khera
+ */
+public final class RandomizedQuickSort {
+
+    private RandomizedQuickSort() {
+        throw new UnsupportedOperationException("Utility class");
+    }
+
+    /**
+     * Sorts the array using the randomized quicksort algorithm.
+     *
+     * @param arr the array to sort
+     * @param low the starting index of the array
+     * @param high the ending index of the array
+     */
+    public static void randomizedQuickSort(int[] arr, int low, int high) {
+        if (low < high) {
+            int pivotIndex = partition(arr, low, high);
+            randomizedQuickSort(arr, low, pivotIndex - 1);
+            randomizedQuickSort(arr, pivotIndex + 1, high);
+        }
+    }
+
+    /**
+     * Partitions the array around a pivot chosen randomly.
+     *
+     * @param arr the array to partition
+     * @param low the starting index
+     * @param high the ending index
+     * @return the index of the pivot after partitioning
+     */
+    private static int partition(int[] arr, int low, int high) {
+        int pivotIndex = low + (int) (Math.random() * (high - low + 1));
+        int pivotValue = arr[pivotIndex];
+        swap(arr, pivotIndex, high); // Move pivot to end
+        int storeIndex = low;
+        for (int i = low; i < high; i++) {
+            if (arr[i] < pivotValue) {
+                swap(arr, storeIndex, i);
+                storeIndex++;
+            }
+        }
+        swap(arr, storeIndex, high); // Move pivot to its final place
+        return storeIndex;
+    }
+
+    /**
+     * Swaps two elements in the array, only if the indices are different.
+     *
+     * @param arr the array in which elements are to be swapped
+     * @param i the first index
+     * @param j the second index
+     */
+    private static void swap(int[] arr, int i, int j) {
+        // Skip if indices are the same
+        if (i == j) {
+            return;
+        }
+        int temp = arr[i];
+        arr[i] = arr[j];
+        arr[j] = temp;
+    }
+}
diff --git a/src/test/java/com/thealgorithms/randomized/RandomizedQuickSortTest.java b/src/test/java/com/thealgorithms/randomized/RandomizedQuickSortTest.java
@@ -0,0 +1,44 @@
+package com.thealgorithms.randomized;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Unit tests for the RandomizedQuickSort class.
+ */
+public class RandomizedQuickSortTest {
+
+    /**
+     * Tests sorting of an array with multiple elements, including duplicates.
+     */
+    @Test
+    public void testRandomizedQuickSortMultipleElements() {
+        int[] arr = {3, 6, 8, 10, 1, 2, 1};
+        int[] expected = {1, 1, 2, 3, 6, 8, 10};
+        RandomizedQuickSort.randomizedQuickSort(arr, 0, arr.length - 1);
+        assertArrayEquals(expected, arr);
+    }
+
+    /**
+     * Tests sorting of an empty array.
+     */
+    @Test
+    public void testRandomizedQuickSortEmptyArray() {
+        int[] arr = {};
+        int[] expected = {};
+        RandomizedQuickSort.randomizedQuickSort(arr, 0, arr.length - 1);
+        assertArrayEquals(expected, arr);
+    }
+
+    /**
+     * Tests sorting of an array with a single element.
+     */
+    @Test
+    public void testRandomizedQuickSortSingleElement() {
+        int[] arr = {5};
+        int[] expected = {5};
+        RandomizedQuickSort.randomizedQuickSort(arr, 0, arr.length - 1);
+        assertArrayEquals(expected, arr);
+    }
+}
