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

Введение

Сортировка методом пузырька (Bubble Sort) очень проста в объяснении и реализации - мы просто бегаем в цикле по парам и обмениваем их местами, по окончании циклов массив будет отсортирован, ниже реализация на C#:

    public static void BubbleSort()
    {
        byte[] Gbytes = File.ReadAllBytes(".\file.txt");
        for (int i = 0; i < Gbytes.Length; i++)
        {
            for (int j = 0; j < Gbytes.Length - 1; j++)
            {
                if (Gbytes[j] > Gbytes[j + 1])
                {
                    byte t = Gbytes[j + 1];
                    Gbytes[j + 1] = Gbytes[j];
                    Gbytes[j] = t;
                }
            }
        }
        File.WriteAllBytes("file_BubbleSort.txt", Gbytes);
    }

Опишу происходящее в коде, многое будет неизменным в следующих реализациях. Массив Gbytes[] получен путём загрузки текстового файла file.txt, цикл по i говорит о количестве итераций необходимых для полной сортировки массива, а цикл j перебирает пары и меняет их местами. Результирующий файл по окончании сохраняется на диск.

Оптимизация 1 - не трогать уже отсортированное

Так как для сортировки мы вынуждены проходить массив i*j раз, то процесс очень затягивается даже не на сильно больших данных (в конце тестовые файлы размером в 50 Кб сортируются за минуты, что на фоне C# сортировки Array.Sort() работающей миллисекунды - выглядит удручающе). Первая очевидная оптимизация заключается в том, что самый "тяжёлый" элемент массива за один проход будет проталкиваться в конец. Иногда говорят что это "камешек тонет". Зная это можно после каждого прохода внутренний цикл уменьшать на значение i, то есть работать только с неотсортированными данными:

public static void BubbleSort()
{
    byte[] Gbytes = File.ReadAllBytes(".\file.txt");
    for (int i = 0; i < Gbytes.Length; i++)
    {
        for (int j = 0; j < Gbytes.Length - i - 1; j++) // <-- изменено
        {
            if (Gbytes[j] > Gbytes[j + 1])
            {
                byte t = Gbytes[j + 1];
                Gbytes[j + 1] = Gbytes[j];
                Gbytes[j] = t;
            }
        }
    }
    File.WriteAllBytes("file_BubbleSort.txt", Gbytes);
}

В шестой строке мы заменили Gbytes.Length-1 на Gbytes.Length-i-1, что позволило каждый i-ый цикл уменьшать на один и не трогать отсортированные крайние значения в конце массива.

Оптимизация 2 - отслеживание обменов

Одним из критериев отсортированности массива является отсутствие обменов за проход внутреннего цикла. Вводим переменную swapped для отслеживания этого состояния и прекращаем сортировку если ни одного обмена не было. Выигрыш по скорости прямо пропорционален степени отсортированности массива на старте - на полностью отсортированном массива цикл по i пройдёт только один раз:

public static void BubbleSort()
{
    byte[] Gbytes = File.ReadAllBytes(".\file.txt");
    for (int i = 0; i < Gbytes.Length; i++)
    {
        bool swapped = false; // <-- добавлено
        for (int j = 0; j < Gbytes.Length - i - 1; j++)
        {
            if (Gbytes[j] > Gbytes[j + 1])
            {
                swapped = true; // <-- добавлено
                byte t = Gbytes[j + 1];
                Gbytes[j + 1] = Gbytes[j];
                Gbytes[j] = t;
            }
        }
        if (!swapped) break; // <-- добавлено
    }
    File.WriteAllBytes("file_BubbleSort.txt", Gbytes);
}

Для каждой итерации i мы сбрасываем swapped, а меняем значение в зоне if() если хотя бы одна перестановка случается. После прохода цикла проверяем были ли перестановки и если нет, то прерываем цикл по i.

Оптимизация 3 - шейкерная сортировка (Cocktail Sort)

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

public static void CoctailSort()
{
    int left_idx = 0; // <-- позиция несортированных данных в начале массива
    int right_idx = Gbytes.Length - 1; // <-- ... в конце массива
    while (true)
    {
        bool swapped = false; // <-- признак состоявшегося обмена в массиве
        for (int i = left_idx; i < right_idx; i++) // топим тяжёлые элементы
        {
            if (Gbytes[i] > Gbytes[i + 1])
            {
                swapped = true;
                byte t = Gbytes[i + 1];
                Gbytes[i + 1] = Gbytes[i];
                Gbytes[i] = t;
            }
        }
        right_idx--; // сдвигаем границу
        if ((left_idx < right_idx) && swapped)
        { // если границы сортировки не смкнулись и были обмены, то продолжаем сортировку
            swapped = false;
            for (int j = right_idx; j > left_idx; j--) // выталкиваем лёгкие элементы
            {
                if (Gbytes[j] < Gbytes[j - 1])
                {
                    swapped = true;
                    byte t = Gbytes[j - 1];
                    Gbytes[j - 1] = Gbytes[j];
                    Gbytes[j] = t;
                }
            }
            left_idx++; // сдвигаем границу
            if (!swapped || (left_idx == right_idx)) break; // аналогично строке 19 проверяем на смыкание границ и на отсутствие перестановок
        }
        else break; // если условие в 19 строке не выполняется, то массив отсортирован
    }
    File.WriteAllBytes("file_CoctailSort.txt", Gbytes);
}

Я сделал общий бесконечный цикл и условие его прерывания, а внутри цикл по i топит тяжёлые элементы массива, а цикл j выталкивает лёгкие. Применяются обе предыдущие пузырьковые оптимизации - следим за границами уже сортированных данных с помощью переменных left_idx и right_idx, а так же swapped отслеживает факт обмена.

Оптимизация 4 - авторская (камешек в болоте или swamp pebble)

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

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

public static void SwampPebbleSort()
{
    for (int j = 0; j < Gbytes.Length - 1; j++)
    {
        if (Gbytes[j] > Gbytes[j + 1])
        {
            byte t = Gbytes[j + 1];
            Gbytes[j + 1] = Gbytes[j];
            Gbytes[j] = t;
            for (int v = j; v > 0; v--)
            {
                if (Gbytes[v] < Gbytes[v - 1])
                {
                    t = Gbytes[v - 1];
                    Gbytes[v - 1] = Gbytes[v];
                    Gbytes[v] = t;
                }
            }
        }
    }
    File.WriteAllBytes("file_SwampPebbleSort.txt", Gbytes);
}

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

Результат

Сводная таблица, где я взял за основу искусственно созданные файлы и уже мой любимый текстовый файл "20000 Leagues Under the Sea.txt":

Используемые файлы:

Вопрос к читателям

Почему Cocktail Sort "слился" на part_sorted_50000 обычному пузырьку?

Содержимое файла выглядит так, рандомно-генерированный файл на 50000 байт из двух символов:

iiii{i{i{{{{{i{ii{i{i{{iii{i{i{iii{

Пока не делал распечатку всех итераций чтобы сравнить, число обменов одинаковое 311698004, а вот число итераций циклов у Cocktail Sort больше чем у Bubble Sort - 937774940 против 932240345.