TheAlgorithms · yanglbme · Jul 6, 2019 · Jul 6, 2019 · Jul 6, 2019
@@ -33,12 +33,27 @@ public <T extends Comparable<T>> T[] sort(T[] array) {

    private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
        if (left < right) {
-            int pivot = partition(array, left, right);
+            int pivot = randomPartition(array, left, right);
            doSort(array, left, pivot - 1);
            doSort(array, pivot, right);
        }
    }

+    /**
+     * Ramdomize the array to avoid the basically ordered sequences
+     * 
+     * @param array The array to be sorted
+     * @param left  The first index of an array
+     * @param right The last index of an array
+     * @return the partition index of the array
+     */
+
+    private static <T extends Comparable<T>> int randomPartition(T[] array, int left, int right) {
+        int randomIndex = left + (int)(Math.random()*(right - left + 1));
+        swap(array, randomIndex, right);
+        return partition(array, left, right);
+    }
+
    /**
     * This method finds the partition index for an array
     *
@@ -75,7 +90,7 @@ public static void main(String[] args) {
        Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};

        QuickSort quickSort = new QuickSort();
-        // quickSort.sort(array);
+        quickSort.sort(array);

        //Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111
        print(array);