Написав предыдущую статью о сортировке подсчётом 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;
}
else break;
}
}
}
File.WriteAllBytes("file_SwampPebbleSort.txt", Gbytes);
}В такой реализации не требуется проверять на обмены посредством переменной swapped, а каждый цикл по v лёгкие элементы передвигает в начало, а тяжёлые на одну позицию к концу, поэтому по окончании j весь массив будет отсортирован.
Результат
Сводная таблица, где я взял за основу искусственно созданные файлы и уже мой любимый текстовый файл "20000 Leagues Under the Sea.txt":
Используемые файлы:
| 50000 байт заполненные одним значением |
| 50000 байт заполненные случайно двумя значениями |
| Весь файл заполнен одним значением, первый байт большего значения |
| 50000 случайных значений в выборке из 256 |
| ASCII копия книги "20000 Leagues Under the Sea" на английском языке (841313 байт) |
Вопрос к читателям
Почему Cocktail Sort "слился" на part_sorted_50000 обычному пузырьку?
Содержимое файла выглядит так, рандомно-генерированный файл на 50000 байт из двух символов:
iiii{i{i{{{{{i{ii{i{i{{iii{i{i{iii{
Пока не делал распечатку всех итераций чтобы сравнить, число обменов одинаковое 311698004, а вот число итераций циклов у Cocktail Sort больше чем у Bubble Sort - 937774940 против 932240345.
Дополнение
Добрались руки до бинарного поиска (спасибо за комментарий пользователю LaRN), для проверки не стал писать/копировать свою реализацию, воспользовался Array.BinarySearch(), после нахождения места для вставки - сдвигаю массив вправо и делаю обмен. Код ниже заменяет собой весь цикл for (int v = j; v > 0; v--). Тут j-ый элемент массива - кандидат на вставку в отсортированный интервал [0, j-1].
var ret = Array.BinarySearch(Gbytes, 0, j, t);
if (ret < 0) ret = ~ret;
if (ret >= 0)
{
for (int w = j; w > ret; w--)
{
Gbytes[w] = Gbytes[w - 1];
}
Gbytes[ret] = t;
}Время сортировки изменилось:
sorted_50000 | part_sorted_50000 | start_50000 | random256_50000 | 20000 Leagues Under the Sea | |
Было | 0 | 488 | 2 | 986 | 263018 |
Стало | 0 | 271 | 541 | 531 | 150472 |
Заметна разница (ускорение) в работе на случайных несортированных данных и ожидаемо "провал" на файле с "черепахой" в начале массива, файл start_50000.
Как очевидное развитие такого метода - проверка крайних значений отсортированной части массива, то есть мы исходим из того, что значение t может быть либо меньше всего, что сортировалось ранее, либо - больше. Если больше, то ничего делать не нужно, а если меньше, то нужно сразу делать вставку на место первого элемента массива.
if (t < Gbytes[j - 1]) // искать место для вставки только если t меньше максимального элемента массива
{
if (t >= Gbytes[0]) // если t больше или равно минимального жлемента, то искать место бинарным поиском
{
var ret = Array.BinarySearch(Gbytes, 0, j, t); // бинарный поиск
if (ret < 0) ret = ~ret; // если не найдено, то получаем указатель на ближайшее большее значение
if (ret >= 0)
{
for (int w = j; w > ret; w--) // сдвиг элементов вправо
{
Gbytes[w] = Gbytes[w - 1];
}
Gbytes[ret] = t; // вставка
}
}
else // иначе t нужно поменять с крайним левым элементом массива и все остальные сдвинуть вправо
{
for (int w = j; w > 0; w--) // сдвиг элементов вправо
{
Gbytes[w] = Gbytes[w - 1];
}
Gbytes[0] = t; //вставка
}
}Как результат:
sorted_50000 | part_sorted_50000 | start_50000 | random256_50000 | 20000 Leagues Under the Sea | |
Было | 0 | 271 | 541 | 531 | 150472 |
Стало | 0 | 266 | 0 | 531 | 149931 |
На start_50000 была устранена проблема с "черепахой".
Замечу, что проверка if (t >= Gbytes[0]) без условия равенства замедлит работу с данными вида ТAAТТAТAAAAAТAAТAТТAAAТ(это шаблон part_sorted_50000). Связано это с тем, что слева будут накапливаться элементы массива одного значения и вместо постоянного сдвига всех элементов слева лучше найти позицию для вставки (то есть в частично отсортированном массиве, например таком AAAТТТТ*AAAAAТAAТAТТAAAТ, здесь звездой я пометил позицию j основного цикла сортировки, мы можем букву A поставить на первую позицию слева и сдвинуть массив на 7 позиций вправо или на 4-ю позицию и сдвигать потребуется только 4 элемента массива), а случай с полным копированием оставить только для одного крайнего условия.