Модификации сортировки пузырьком

Написав предыдущую статью о сортировке подсчётом 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.