Оптимизация быстрой сортировки, когда в массиве много дубликатов

Question

У меня есть вопрос прошлого года, основанный на следующем сценарии:

Когда список сортируемых элементов содержит много повторяющихся значений, мы можем улучшить QuickSort, сгруппировав все значения, равныеПовернитесь к середине, а затем мы рекурсивно выберем эти значения слева и те значения справа.Для достижения этого внесите необходимые изменения в метод разбиения.

Вот используемая в настоящее время реализация:

// Quick Sort algorithm
public class QuickSort {

    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length-1);
    }

    private static void quickSort(int[] a, int i, int j) {
        if (i < j) {
            int pivotIdx= partition(a, i, j);
            quickSort(a, i, pivotIdx-1);
            quickSort(a, pivotIdx+1, j);
        }
    }

    private static void swap(int[] a, int pos1, int pos2) {
        int temp = a[pos1];
        a[pos1] = a[pos2];
        a[pos2] = temp;
    }

    private static int partition(int[] a, int i, int j) {
        // partition data items in a[i..j]
        int p = a[i]; // p is the pivot, the i-th item
        int m = i;    // Initially S1 and S2 are empty

        for (int k=i+1; k<=j; k++) { // process unknown region
            if (a[k] < p) { // case 2: put a[k] to S1
                m++;
                swap(a,k,m);
            }
        }

        swap(a,i,m); // put the pivot at the right place
        return m;    // m is the pivot's final position
    }

    public static void printArray(int[] a) {
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 7, 12, 3, 5, -6, 3, 8, 2, 10, -3 };

        printArray(arr);
        quickSort(arr);
        printArray(arr);
    }
}

У меня есть некоторое базовое понимание алгоритма быстрой сортировки, представленного здесь, но я не совсем понимаю, действительно ли вопрос подсказал мне, какреализовать алгоритм, потому что, по моему мнению, быстрая сортировка должна выполнить итерацию по списку, чтобы сделать 2 разбиения, и динамически решить положение X, куда поместить точку поворота, которая в этой реализации выбрана в качестве самого левого элемента входного массива.Если эта позиция X определяется динамически, как именно вы «группируете элементы, равные оси вращения», в середину и как именно она улучшает алгоритм?

Answer 1

Основная идея состоит в том, чтобы решить эту проблему, используя стратегию трехстороннего разделения. Подробнее см. Проблема национального флага Нидерландов .

Если у вас естьмного дублирующих элементов, тогда ваша быстрая сортировка попытается поместить каждый из дублирующих элементов отдельно в правильное положение.Но вам не нужно этого делать.

Давайте рассмотрим пример того, что я заявлял в приведенном выше утверждении:

Предположим, у вас есть массив, подобный {4,6,4,3,4,2,5,4,1,4}.В этом массиве у вас есть элемент 4, повторяющийся 5 раз.А при применении быстрой сортировки и размещении 4 в правильном положении, вы разделите массив на 2 части так, чтобы левая часть содержала все элементы, меньшие или равные 4 (но в произвольном порядке), иправая часть содержит все элементы больше 4.Но это наивный подход.

Давайте посмотрим, как мы можем улучшить это (учитывая, что у нас много повторяющихся элементов)

Когда ваша быстрая сортировка находит 4 и она разбивает массив для размещенияэто 4 в правильном положении, вы также можете отслеживать все равные элементы (другие элементы массива, равные 4) наряду с меньшим слева и большим справа.

Таким образом, при разделении вместо двух индексов left и right (подмассив от 0 до left содержит все элементы, меньшие или равные сводному, а подмассив left до right содержит все элементыбольше чем pivot и right до len(array)-1 - элементы, которые еще предстоит изучить), вы можете иметь 3 индекса, которые описаны ниже:

• [0,left) - подмассив с элементами меньше, чемpivot
• [left, mid) - подмассив с элементами, равными pivot
• [mid, right] - подмассив с элементами больше, чем pivot
• [right, len(array)) - элементы еще не созданыбыть исследованным.

Таким образом, ваша измененная быстрая сортировка будет поворачиваться только меньшее количество раз (в частности, равное количеству уникальных элементов в массиве).И из-за этого будет меньше рекурсивных вызовов.

Таким образом, это решение использует случай для конкретных входных данных, когда имеется много дубликатов (и поэтому, чем больше дублирующихся элементов в вашем массиве, тем лучше это изменениебудет выполнен вариант быстрой сортировки)

Покажите мне какой-нибудь код .

import java.util.Arrays;
import java.util.stream.IntStream;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 4, 1, 2, 4, 3, 5, 6, 2, 2, 2, 1, 1, 1};
        quickSort(arr);
        System.out.print("Sorted array: ");
        Arrays.stream(arr).forEach(i -> System.out.print(i + " "));
        System.out.println();
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start > end)
            return; // base condition

        System.out.print("Recursive call on: ");
        IntStream
                .rangeClosed(start, end)
                .map(i -> arr[i])
                .forEach(i -> System.out.print(i + " "));
        System.out.println();

        int n = arr.length;
        if (start < 0 || start >= n || end < 0 || end >= n)
            throw new IllegalArgumentException("the indices of the array are not valid");

        int pivot = arr[end];
        /*
            [start,left) - sub-array with elements lesser than pivot
            [left, mid) - sub-array with elements equal to pivot
            [mid, right] - sub-array with elements greater than pivot
            [right, end) - elements yet to be explored.
         */
        int left = start, mid = start, right = start;

        while (right != end) {
            if (arr[right] < pivot) {
                swap(arr, left, right);
                swap(arr, mid, right);
                left++;
                right++;
                mid++;
            } else if (arr[right] == pivot) {
                swap(arr, mid, right);
                mid++;
                right++;
            } else if (arr[right] > pivot) {
                right++;
            }
        }

        swap(arr, mid, right);
        System.out.println("Placed " + pivot + " at it's correct position");
        System.out.println();
        quickSort(arr, start, left - 1);
        quickSort(arr, mid + 1, end);
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

Вывод вышеуказанного кода:

Recursive call on: 2 3 4 1 2 4 3 5 6 2 2 2 1 1 1 
Placed 1 at it's correct position

Recursive call on: 2 4 3 5 6 2 2 2 3 4 2 
Placed 2 at it's correct position

Recursive call on: 4 3 5 3 4 6 
Placed 6 at it's correct position

Recursive call on: 4 3 5 3 4 
Placed 4 at it's correct position

Recursive call on: 3 3 
Placed 3 at it's correct position

Recursive call on: 5 
Placed 5 at it's correct position

Sorted array: 1 1 1 1 2 2 2 2 2 3 3 4 4 5 6 

вышеприведенный вывод ясно показывает, что после размещения пивота в его правильном положении, мы рекурсивно перебираем два разных массива, но ни один из этих двух массивов не содержит предыдущий пивот.(Это оптимизация)