«1. Обзор

Сложность алгоритмов во время выполнения часто зависит от характера входных данных.

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

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

2. Простая быстрая сортировка

Быстрая сортировка — это эффективный алгоритм сортировки, основанный на парадигме «разделяй и властвуй». С функциональной точки зрения, он работает с входным массивом на месте и переставляет элементы с помощью простых операций сравнения и замены.

2.1. Разбиение по одной оси

Тривиальная реализация алгоритма быстрой сортировки сильно зависит от процедуры разбиения по одной оси. Другими словами, разбиение делит массив A=[ap, ap+1, ap+2,…, ar] на две части A[p..q] и A[q+1..r] таким образом, что:

    Все элементы в первом разделе, A[p..q] меньше или равны опорному значению A[q] Все элементы во втором разделе, A[q+1..r] больше или равны равно опорному значению A[q]

После этого два раздела обрабатываются как независимые входные массивы и передаются алгоритму быстрой сортировки. Давайте посмотрим на быструю сортировку Ломуто в действии:

2.2. Производительность с повторяющимися элементами

Допустим, у нас есть массив A = [4, 4, 4, 4, 4, 4, 4], в котором все элементы равны.

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

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

3. Трехстороннее разбиение

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

    Крайний левый раздел содержит элементы, строго меньшие ключа разделения Средний раздел содержит все элементы, равные ключу разделения Правый раздел -most partition содержит все элементы, которые строго больше, чем ключ разделения

Теперь мы углубимся в пару подходов, которые мы можем использовать для достижения трехстороннего разделения.

4. Подход Дейкстры

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

4.1. Задача о голландском национальном флаге

Вдохновленный трехцветным флагом Нидерландов, Эдсгер Дейкстра предложил задачу программирования под названием «Задача о голландском национальном флаге» (DNF).

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

Интересно, что проблема DNF делает поразительную аналогию с трехсторонним разбиением массива с повторяющимися элементами.

Мы можем разделить все числа массива на три группы по заданному ключу:

    Красная группа содержит все элементы, строго меньшие ключа Белая группа содержит все элементы, равные ключу Группа Blue содержит все элементы, которые строго больше ключа

4.2. Алгоритм

Один из подходов к решению проблемы DNF состоит в том, чтобы выбрать первый элемент в качестве ключа разделения и просмотреть массив слева направо. Когда мы проверяем каждый элемент, мы перемещаем его в правильную группу, а именно «Меньше», «Равно» и «Больше».

«Чтобы отслеживать процесс разбиения, нам понадобится помощь трех указателей, а именно lt, current и gt. В любой момент времени элементы слева от lt будут строго меньше ключа разбиения, а элементы справа от gt будут строго больше ключа.

Далее мы будем использовать текущий указатель для сканирования, а это значит, что все элементы, лежащие между текущим указателем и указателем gt, еще предстоит исследовать:

Для начала мы можем установить указатели lt и current в самом начало массива и указатель gt в самом его конце:

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

    Если input[current ] \u003c key, то мы меняем input[current] и input[lt] и увеличиваем оба указателя current и lt Если input[current] == ​​key, то мы увеличиваем текущий указатель Если input[current] \u003e key, то мы меняем input[ current] и input[gt] и decrement gt

В конце концов, мы остановимся, когда указатели current и gt пересекутся. При этом размер неисследованной области уменьшается до нуля, и у нас остается всего три необходимых раздела.

Наконец, давайте посмотрим, как этот алгоритм работает с входным массивом, имеющим повторяющиеся элементы:

4.3. Реализация

Во-первых, давайте напишем вспомогательную процедуру с именем compare() для трехстороннего сравнения двух чисел: 

public static int compare(int num1, int num2) {
    if (num1 > num2)
        return 1;
    else if (num1 < num2)
        return -1;
    else
        return 0;
}

Затем добавим метод swap() для обмена элементами по двум индексам числа. тот же массив: 

public static void swap(int[] array, int position1, int position2) {
    if (position1 != position2) {
        int temp = array[position1];
        array[position1] = array[position2];
        array[position2] = temp;
    }
}

Чтобы однозначно идентифицировать раздел в массиве, нам понадобятся его левый и правый граничные индексы. Итак, давайте продолжим и создадим класс Partition: 

public class Partition {
    private int left;
    private int right;
}

Теперь мы готовы написать нашу трехэтапную процедуру partition(): 

public static Partition partition(int[] input, int begin, int end) {
    int lt = begin, current = begin, gt = end;
    int partitioningValue = input[begin];

    while (current <= gt) {
        int compareCurrent = compare(input[current], partitioningValue);
        switch (compareCurrent) {
            case -1:
                swap(input, current++, lt++);
                break;
            case 0:
                current++;
                break;
            case 1:
                swap(input, current, gt--);
                break;
        }
    }
    return new Partition(lt, gt);
}

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

public static void quicksort(int[] input, int begin, int end) {
    if (end <= begin)
        return;

    Partition middlePartition = partition(input, begin, end);

    quicksort(input, begin, middlePartition.getLeft() - 1);
    quicksort(input, middlePartition.getRight() + 1, end);
}

5. Подход Бентли-Макилроя

Джон Бентли и Дуглас Макилрой являются соавторами оптимизированной версии алгоритма Quicksort. Разберемся и реализуем этот вариант на Java:

5.1. Схема разбиения

Суть алгоритма заключается в схеме разбиения, основанной на итерациях. Вначале весь массив чисел является для нас неизведанной территорией:

Затем мы начинаем исследовать элементы массива слева и справа. Всякий раз, когда мы входим или выходим из цикла исследования, мы можем визуализировать массив как композицию из пяти областей:

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

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

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

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

5.2. Реализация

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

public static Partition partition(int input[], int begin, int end){
	// returns partition window
}

«

«Для простоты мы можем выбрать значение разбиения как последний элемент массива. Кроме того, давайте определим две переменные left=begin и right=end для изучения массива внутрь.

Кроме того, нам также нужно отслеживать количество одинаковых элементов, лежащих слева и справа. Итак, давайте инициализируем leftEqualKeysCount=0 и rightEqualKeysCount=0, и теперь мы готовы исследовать и разбивать массив.

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

while (true) {
    while (input[left] < partitioningValue) left++; 
    
    while (input[right] > partitioningValue) {
        if (right == begin)
            break;
        right--;
    }

    if (left == right && input[left] == partitioningValue) {
        swap(input, begin + leftEqualKeysCount, left);
        leftEqualKeysCount++;
        left++;
    }

    if (left >= right) {
        break;
    }

    swap(input, left, right);

    if (input[left] == partitioningValue) {
        swap(input, begin + leftEqualKeysCount, left);
        leftEqualKeysCount++;
    }

    if (input[right] == partitioningValue) {
        swap(input, right, end - rightEqualKeysCount);
        rightEqualKeysCount++;
    }
    left++; right--;
}

На каждой итерации мы перемещаем элементы, равные partitioningValue, к двум концам и увеличиваем соответствующий счетчик: 

right = left - 1;
for (int k = begin; k < begin + leftEqualKeysCount; k++, right--) { 
    if (right >= begin + leftEqualKeysCount)
        swap(input, k, right);
}
for (int k = end; k > end - rightEqualKeysCount; k--, left++) {
    if (left <= end - rightEqualKeysCount)
        swap(input, left, k);
}

На следующем этапе нам нужно переместить все равные элементы с двух концов в центр. После выхода из цикла левый указатель будет находиться на элементе, значение которого не меньше, чем partitioningValue. Используя этот факт, мы начинаем перемещать равные элементы с двух концов к центру: 

return new Partition(right + 1, left - 1);

На последнем этапе мы можем вернуть границы среднего раздела:

Наконец, давайте посмотрим при демонстрации нашей реализации на примере входных данных

6. Анализ алгоритма

В целом алгоритм быстрой сортировки имеет временную сложность в среднем O(n*log(n)) и временную сложность в наихудшем случае О(n2). При высокой плотности повторяющихся ключей мы почти всегда получаем наихудшую производительность при тривиальной реализации быстрой сортировки.

Однако, когда мы используем вариант быстрой сортировки с трехсторонним разделением, например разделение DNF или разделение Bentley, мы можем предотвратить негативное влияние дублирующихся ключей. Кроме того, по мере увеличения плотности повторяющихся ключей производительность нашего алгоритма также улучшается. В результате мы получаем наилучшую производительность, когда все ключи равны, и мы получаем один раздел, содержащий все одинаковые ключи за линейное время.

Тем не менее, мы должны отметить, что мы существенно увеличиваем нагрузку, когда переключаемся на трехстороннюю схему секционирования с тривиальной схемы секционирования с одной точкой опоры.

Для подхода на основе DNF накладные расходы не зависят от плотности повторяющихся ключей. Таким образом, если мы используем разбиение DNF для массива со всеми уникальными ключами, мы получим низкую производительность по сравнению с тривиальной реализацией, в которой мы оптимально выбираем опорную точку.

Но подход Bentley-McIlroy делает умную вещь, поскольку накладные расходы на перемещение одинаковых ключей с двух крайних концов зависят от их количества. В результате, если мы используем этот алгоритм для массива со всеми уникальными ключами, даже тогда мы получим достаточно хорошую производительность.

Таким образом, временная сложность в наихудшем случае как алгоритмов разбиения с одной опорной точкой, так и алгоритмов разбиения по трем направлениям составляет O(nlog(n)). Однако реальная выгода видна в наилучших сценариях, когда мы видим, что временная сложность увеличивается от O(nlog(n)) для разбиения с одной опорой до O(n) для разбиения по трем направлениям.

7. Заключение

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

Желая решить эту проблему, мы изучили различные схемы трехстороннего разбиения и то, как мы можем реализовать их в Java.