Написав предыдущую статью о сортировке подсчётом 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 элемента массива), а случай с полным копированием оставить только для одного крайнего условия.
