Алгоритмы сортировки массивов. Внутренняя сортировка
В данной статье рассматриваются алгоритмы сортировки массивов. Для начала представляются выбранные для тестирования алгоритмы с кратким описанием их работы, после чего производится непосредственно тестирование, результаты которого заносятся в таблицу и производятся окончательные выводы.
Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).
В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.
Для проведения исследования были выбраны следующие алгоритмы сортировки:
Selection sort (сортировка выбором) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2).
Bubble sort (сортировка пузырьком) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2).
Insertion sort (сортировка вставками) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).
Quick sort (быстрая сортировка) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n).
Comb sort (сортировка расческой) – идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n).
Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм.
Полностью неотсортированный массив:
Частично отсортированный массив (половина элементов упорядочена):
Результаты, предоставленые в графиках:
В результате проведенного исследования и полученных данных, для сортировки неотсортированного массива, наиболее оптимальным из представленных алгоритмов для сортировки массива является быстрая сортировка. Несмотря на более длительное время выполнения алгоритм потребляет меньше памяти, что может быть важным в крупных проектах. Однако такие алгоритмы как сортировка выбором, обменом и вставками могут лучше подойти для научных целей, например, в обучении, где не нужно обрабатывать огромное количество данных. При частично отсортированном массиве результаты не сильно отличаются, все алгоритмы сортировки показывают время примерно на 2-3 миллисекунды меньше. Однако при сортировке частично отсортированного массива быстрая сортировка срабатывает намного быстрее и потребляет меньшее количество памяти.
Если вы программируете и ваш код уходит дальше написания калькулятора, ты вы не раз столкнётесь или сталкивались с необходимостью отсортировать тот или иной массив данных. Существует множество способов сортировки. В этой статье мы разберём основные из них и сделаем акцент на быстрой сортировке.
Понятие быстрой сортировки
Быстрая сортировка - Quick Sort или qsort. По названию становится понятно, что это и для чего. Но если не понятно, то это алгоритм по быстрой сортировке массива, алгоритм имеет эффективность O(n log n) в среднем. Что это значит? Это значит, что среднее время работы алгоритма повышается по той же траектории, что и график данной функции. В некоторых популярных языках имеются встроенные библиотеки с этим алгоритмом, а это уже говорит о том, что он крайне эффективен. Это такие языки, как Java, C++, C#.
Алгоритм
Метод быстрой сортировки использует рекурсию и стратегию "Разделяй и властвуй".
1. В массиве ищется некий опорный элемент, для простоты лучше взять центральный, но если вы хотите поработать над оптимизацией, то придётся попробовать разные варианты.
2. Слева от опоры ищется элемент больший, чем опорный, справа - меньший, чем опорный, затем меняем их местами. Делаем это, пока максимальный справа не будет меньше, чем минимальный слева. Таким образом, все маленькие элементы кидаем в начало, большие - в конец.
3. Рекурсивно применяем данный алгоритм к левой и правой части нашего алгоритма отдельно, затем ещё и ещё, до достижения одного элемента или определённого количества элементов. Что же это за количество элементов? Есть ещё один способ оптимизировать данный алгоритм. Когда сортируемая часть становится примерно равной 8 или 16, то можно обработать её обычной сортировкой, например пузырьковой. Так мы повысим эффективность нашего алгоритма, т.к. маленькие массивы он обрабатывает не так быстро, как хотелось бы.
Таким образом, будет обработан и отсортирован весь массив. А теперь наглядно изучим данный алгоритм
Эффективность быстрой сортировки
Является ли быстрая сортировка самым быстрым алгоритмом сортировки? Однозначно нет. Сейчас появляется всё больше и больше сортировок, на данный момент самая быстрая сортировка - это Timsort, она работает крайне быстро для массивов, изначально отсортированных по-разному. Но не стоит забывать, что метод быстрой сортировки является одним из самых простых в написании, это очень важно, ведь, как правило, для рядового проекта нужно именно простое написание, а не громадный алгоритм, который сам ты и не напишешь. Timsort - тоже не самый сложный алгоритм, но звание самого простого ему точно не светит.
Реализация алгоритма
Ну вот мы и дошли до самого "вкусного". Теперь разберём, как реализовывается данный алгоритм. Как говорилось ранее, он не слишком сложен в реализации, скорее, даже прост. Но мы всё равно полностью разберём каждое действие нашего кода, чтобы вы поняли, как работает быстрая сортировка.
Наш метод называется quickSort. В нём запускается основной алгоритм, в который мы передаём массив, первый и последний его элементы. Запоминаем в переменные i и k первый и последний элемент сортируемого отрезка, чтобы не изменять эти переменные, так как они нам нужны. Затем проверяем расстояние между первым и последним проверяемым: оно больше или равно единице? Если нет, значит, мы пришли к центру и нужно выйти из сортировки этого отрезка, а если да, то продолжаем сортировку.
Затем за опорный элемент берём первый элемент в сортируемом отрезке. Следующий цикл делаем до того момента, пока не дойдём до центра. В нём делаем ещё два цикла: первый - для левой части, а второй - для правой. Их мы выполняем, пока есть элементы, подходящие под условие, или пока не дойдём до опорного элемента. Затем, если минимальный элемент всё же справа, а максимальный - слева, меняем их местами. Когда цикл заканчивается, меняем первый элемент и опорный, если опорный меньше. Затем мы рекурсивно делаем наш алгоритм для правого и левого участка массива и так продолжаем, пока не дойдём до отрезка длиной в 1 элемент. Тогда все наши рекурсивные алгоритмы будут return, и мы полностью выйдем из сортировки. Также внизу имеется метод swap - вполне стандартный метод при сортировке массива заменами. Чтобы несколько раз не писать замену элементов, пишем один раз и меняем элементы в данном массиве.
В заключение можно сказать, что по соотношению "качество-сложность" быстрая сортировка находится на лидирующей позиции среди всех алгоритмов, поэтому вам стоит однозначно взять метод на заметку и использовать при необходимости в своих проектах.
Сортировка Шелл.
Представляет собой модификацию метода вставок. Используются сравнения и перестановки элементов, но в отличие от метода вставок, в сравнении участвуют не соседние, а отстоящие друг от друга на определенном расстоянии элементы. При необходимости перестановки, элементы перемещаются скачком на данное расстояние, а не на одну позицию.
В одной из модификаций метода (в случае, предложенном Д. Шеллом) шаг кратен степеням двойки. Вначале последовательность из N элементов делится на N/2 групп, если N – четно, и на (N-1)/2 групп, если N – нечетно. Каждая группа содержит по два элемента, если количество элементов было нечетным, одна из групп содержит три элемента. Элементы каждой группы отстоят друг от друга на расстоянии N/2 или (N-1)/2. В течение первого прохода осуществляется упорядочение элементов каждой группы методом вставок. Для осуществления следующего прохода шаг уменьшается вдвое (как и число групп), по отношению к предыдущему шагу (у дробных чисел берется целая часть). Процесс повторяется до тех пор, пока шаг не станет равным единице. В этом случае методом вставок сортируется весь список (одна группа). С точки зрения программной реализации потребуется неоднократный вызов сортировки вставками с указанием, в качестве параметров (помимо исходного списка и числа элементов), индекса начального элемента группы и шага. Приблизительное число сравнений составляет N log 2 N.
// Функция сортировки Шелла целочисленного массива
// Аргументы:
// arr - сортируемый массив
// size - размер сортируемого массива
void SortShell(int* arr, int size) {
int step = size / 2;
while (step != 0) {
// Сортируем группы элементов отстоящих друг от друга на значение шага вставками
for (int i = step; i < size; ++i) {
int tmp = arr[i];
for (j = i - step; j >= 0 && arr[j] > tmp; j -= step)
arr = arr[j];
arr = tmp;
Сортировка выбором
В процессе первого прохода в исходном массиве находятся минимальный элемент, который помещается на место первого элемента. Первый элемент помещается на место минимального. На втором и последующих проходах поиск и обмен повторяются для оставшихся после предыдущего прохода элементов (с позициями: на втором проходе – со второй по последнюю, на третьем проходе – с третьей по последнюю и т.д.) до тех пор, пока не будет отсортирована вся последовательность. Общее число сравнений составляет приблизительно 0,5 N 2 , N – здесь и далее число элементов.
void selectSort(int a, long size) {
for(i=0; i < size; i++) { // i - номер текущего шага
for(j=i+1; j < size; j++) // цикл выбора наименьшего элемента
if (a[j] < x) {
k=j; x=a[j]; // k - индекс наименьшего элемента
a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]
Сортировка пузырьком
В процессе сортировки производится попарное сравнение соседних элементов. Если порядок следования соседних элементов нарушен, то они меняются местами. В процессе первого прохода максимальный элемент попадает на последнее место и, следовательно, в последующих сравнениях не участвует. Остальные элементы "всплывают" на одну позицию вверх (поэтому метод часто называют сортировкой "пузырьком"). На каждом следующем проходе рассматривается последовательность для N-1, N-2 и т.д. элементов. Если при каком-либо проходе не было произведено ни одной перестановки, последовательность отсортирована. Максимальное число сравнений составляет приблизительно 0,5 N 2 , среднее число сравнений пропорционально 0,25 N 2 , среднее число обменов – 0,25 N 2 .
void bubbleSort(int a, long size) {
for(i=0; i < size; i++) { // i - номер прохода
for(j = size-1; j > i; j--) { // внутренний цикл прохода
if (a > a[j]) {
x=a; a=a[j]; a[j]=x;
Сортировка вставками
Первый элемент исходного списка считается отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. В целом, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. Среднее число сравнений пропорционально N 2 .
void insertSort(int a, long size) {
for (i=0; i < size; i++) { // цикл проходов, i - номер прохода
// поиск места элемента в готовой последовательности
for (j=i-1; j>=0 && a[j] > x; j--)
a = a[j]; // сдвигаем элемент направо, пока не дошли
// место найдено, вставить элемент
Метод подсчёта
Метод основан на том, что k+1-ый элемент упорядоченной последовательности превышает ровно k элементов, и следовательно занимает k+1-ую позицию. В процессе сортировки на каждом i-ом проходе i-ый элемент исходной последовательности попарно сравнивается со всеми остальными элементами. Инициализированный нулем перед началом прохода счетчик k увеличивается, если i-ый элемент оказался больше текущего. Таким образом, порядковый номер i-го элемента, по окончанию i-го прохода, равен k+1. Для сортировки последовательности из N элементов требуется N проходов, на каждом из которых выполняется N сравнений. Число сравнений равно N 2 . Приведенный метод подсчета можно использовать,
void insertSort(int a, long size)
int *b=new int;
for
(int
i=0;i for
(int
j=0;j if
(a[i]>a[j]){ Сортировка
по дереву (6)
Процесс
сортировки состоит из: фазы построения
двоичного дерева поиска и фазы обхода.
Структура двоичного дерева задается с
помощью связного списка, каждый элемент
которого может иметь, максимум, двух
потомков (две ссылки). Двоичное дерево
формируется по всем исходным элементам,
по следующему правилу. Первый элемент
исходной последовательности является
первым узлом дерева. Следующий элемент
последовательности сравнивается со
значениями в узлах строящегося дерева,
начиная с корня. Если значение текущего
элемента больше значения элемента в
узле дерева, следует переместиться вниз
по правой ссылке от текущего узла, в
противном случае – по левой ссылке.
Перемещение по дереву продолжается до
тех пор, пока не будет достигнута
свободная ссылка, после чего осуществляется
вставка элемента в дерево. После
формирования дерева необходимо провести
процедуру смешанного обхода. Он
заключается в рекурсивном посещении
(чтении) узлов, начиная с корня: левого
поддерева, узла, правого поддерева. В
результате получается отсортированная
последовательность. Среднее число
сравнений aN log 2
N, 1 < a < 2. Сбалансированное
N-ленточное слияние
Общей
формой внешней сортировки является
N-ленточное слияние. Для N-ленточного
слияния потребуется 2N магнитных лент
и 2N лентопротяжных устройств (которые
можно заменить 2N файлами на устройстве
внешней памяти). Исходная неупорядоченная
последовательность размещается на
первой магнитной ленте. Затем она
разносится на N магнитных лент по
следующему правилу: первая запись – на
первую из N лент, вторая – на вторую,
(N+1)-ая – снова на первую из N лент. Сбалансированное
N-ленточное слияние осуществляется в
два этапа. На первом этапе из записей,
хранящихся на каждой магнитной ленте,
формируются упорядоченные цепочки. Так
как все цепочки имеют одинаковую длину,
слияние называется сбалансированным.
Упорядочение цепочки происходит в
оперативной памяти одним из методов
внутренней сортировки. Упорядоченные
цепочки размещаются на N свободных
магнитных лентах, после чего начинается
второй этап сортировки – слияние.
Процесс слияния осуществляется в
несколько циклов. После каждого цикла
слияния длина упорядоченных цепочек
увеличивается на N.
В конечном итоге, формируется упорядоченная
последовательность из N составляющих.
Собственно слияние осуществляется
следующим образом. Пусть имеются две
цепочки длиной l
,
изначально упорядоченные. Необходимо
получить одну упорядоченную цепочку.
Для этого: сравниваются первые элементы
двух цепочек, меньшая переписывается
в результирующую цепочку; операция
осуществляется с помощью трех счетчиков;
после записи в результирующую
последовательность увеличивается на
единицу счетчик результирующей
последовательности и счетчик
последовательности, в которой был
обнаружен меньший элемент; действие
повторяется до тех пор, пока один из
счетчиков исходной последовательности
не достигнет значения конца
последовательности, после чего оставшиеся
элементы другой последовательности
дописываются в конец результирующей.
Таким образом, будут упорядочены каждая
из N магнитных лент. На днях в комментариях вконтакте у меня возник спор с одним из других студентов проекта. Суть спора заключалась в том, «кто кого» - метод sort() из класса java.util.Arrays или самописные реализации простых алгоритмов: bubble
(пузырьковая), insertion
(вставками), selection
(выбором), shell
(алгоритм Шелла).
Для некоторых ответ на данный вопрос может быть очевиден, но раз спор возник, при том что у каждой из сторон были «уважаемые источники» в пользу своей точки зрения, было принято решение провести исследование, поразмяв в процессе серое вещество, реализуя различные алгоритмы.
TL;DR:
java.util.Arrays.sort() безоговорочно лидирует на массивах от 100 000 элементов, при меньшем размере с ним иногда может потягаться метод Шелла. Остальные рассмотренные алгоритмы сливают вчистую и могут быть полезны лишь при каких-то экзотических условиях.
Теперь давайте рассмотрим, как же осуществляется сортировка массивов в наших убер-девайсах из кремния.
Обектом внешней сортировки является файл. Размеры файла принципиально не ограничены, то есть он может не помещаться в оперативной памяти. Для этого вида сортировки дополнительные расходы внешней памяти жестко не нормируются, поэтому активно используются вспомогательные файлы. Доступ к файлам строго последовательный. Это требование обусловлено двумя обстоятельствами. Во-первых, методы внешней сортировки должны быть работоспособными при хранении файлов на устройствах последовательного доступа типа магнитных лент. Во-вторых, при использовании прямого доступа основные затраты времени связаны с позиционированием файлов, что желательно исключить. В основе методов внешней сортировки лежит процедура слияния, заключающаяся в объединении двух или более отсортированных последовательностей. Рассмотрим эту процедуру на примере слияния двух последовательностей A и B в последовательность C. Пусть элементы A и B отсортированы по возрастанию, то есть a 1 £ a 2 £ …£ a m и b 1 £ b 2 £ …£ b n . Требуется, чтобы последовательность C также располагалась по возрастанию, то есть выполнялось c 1 £ c 2 £ …£ c m + n . Сначала в качестве текущих выбираются первые элементы последовательностей. Меньший из них записывается в C, и вместо него текущим становится следующий элемент этой же последовательности. Эта операция повторяется до исчерпания одной из последовательностей, после чего в C дописывается остаток другой последовательности. Можно заметить, что доступ к элементам A, B и C выполнялся строго последовательно. В методах внешней сортировки в качестве последовательностей A, B и C фигурируют отсортированные участки файлов. Базовым методом внешней сортировки является метод простого слияния. Рассмотрим его на следующем примере. Пусть имеется файл A, включающий элементы 27, 16, 13, 11, 18, 25, 7. Этот файл разделяется на два файла B и C путем поочередной записи элементов в эти файлы. Покажем это схемой B: 27, 13, 18, 7 A: 27, 16, 13, 11, 18, 25, 7 Затем файлы B и C снова соединяются путем поочередного включения в C элементов из A и B. При этом первым располагается меньший элемент каждой пары. Получится следующий результат B: 27, 13, 18, 7 Пары отделяются друг от друга апострофами. На следующем этапе снова происходит разделение файла A на B и C, но в каждый файл пишутся поочередно уже не отдельные элементы, а выделенные пары. Получаем B: 16, 27,’ 18, 25 A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7 B: 16, 27,’ 18, 25 A: 11, 13, 16, 27,’ 7, 18, 25 Затем файл A распределяется по четверкам элементов и при новом соединении будет состоять из упорядоченных восьмерок элементов. В нашем примере сортировка закончится на этом этапе. В общем случае длина отсортированных серий будет увеличиваться по степеням 2, пока величина серии не превзойдет количество элементов в файле. На этом примере определим основные термины внешней сортировки. В методе участвовали 3 файла, поэтому он называется трехленточным. Для выполнения сортировки потребовалось 3 прохода. Отдельный проход состоял из процедур разделения и слияния, каждая из которых обрабатывала все элементы. Такие процедуры называют фазами. Следовательно, метод простого слияния является двухфазным и трехленточным. Есть очевидное усовершенствование метода. Результат слияния сразу распределяется на две ленты, то есть в процессе участвуют уже 4 ленты. За счет дополнительной памяти число операций перезаписи уменьшается вдвое. Это однофазный четырехленточный метод, называемый также сбалансированным слиянием. Как видно из приведенных выше данных, метод может конкурировать по скорости с самыми быстрыми методами внутренней сортировки, но не применяется в таком качестве, так как требует значительных затрат памяти. Число проходов оценивается величиной log 2 n, а общее число пересылок M пропорцинально n log 2 n. Метод простого слияния не дает какого-либо выигрыша в тех случаях, когда файл A полностью либо частично отсортирован. Этот недостаток отсутствует в методе естественного слияния. Назовем серией последовательность элементов a i , a i +1 , …, a j , удовлетворяющих соотношениям a i -1 > a i £ a i +1 £ …£ a j > a j +1 . В частных случаях серия может находиться в начале или конце последовательности. Исходный файл A разбивается на серии. Распределение на B и C ведется по сериям. При соединении сливаются пары серий. Снова возможен как трехленточный, так и четырехленточный вариант метода. Ниже показан пример сортировки методом естественного слияния c 4 лентами. B: 17, 25, 41, ‘6 A: 17, 25, 41, ‘ 9, 11, ‘ 6, ‘ 3, 5, 8, 44 C: 9, 11, ‘ 3, 5, 8, 44 A: 9, 11, 17, 25, 41 B: 3, 5, 6, 8, 9, 11, 17, 25, 41, 44 D: 3, 5, 6, 8, 44 C: При последнем разделении лента C оказывается пустой, и отсортированный файл остается на ленте B. Метод естественного слияния в целом быстрее, но требует большего числа сравнений, так как требуется определять конец каждой серии. Ниже приведена программа сортировки файла двухфазным трехленточным методом естественного слияния. Program SortSlian; { 3-ленточная, 2-фазная сортировка естественным слиянием } { ключи целые и положительные } Type elem=record { другие поля } tape=file of elem; Name: string; { имя исходного файла } Procedure Vvod(var F: tape); While K <> -1 do Write("Введите очередной ключ (конец -1): "); if K<>-1 then Write(F, S) Procedure Pech(var F: tape); While not eof(F) do Write(S. Key," ") Procedure CopyElem(var X, Y: tape; var Buf: elem; var E: boolean); { копирование элемента и считывание следующего { в Buf с проверкой конца серии (E=True) } if not Eof(X) then Read(X, Buf) else Buf.Key:=-1; { барьер: достигнут конец файла } E:=(Buf.Key Procedure CopySer(var X, Y: tape; var Buf: elem); { копирование серии из X в Y } {в начале Buf-первый элемент текущей серии на X } {в конце Buf-первый элемент следующей или –1 (конец X) } if Buf.Key>0 then { файл X не считан } CopyElem(X, Y, Buf, E) Until E { E=True в конце серии } Procedure Raspred; { распределение A ---> B и C } Read(A, S); { первый элемент из A } Rewrite(B); Rewrite(C); CopySer(A, B, S); {S-первый элемент следующей серии } if S.Key>0 then { файл A скопирован не весь } CopySer(A, C, S) Until S.Key<0 Procedure Slian; { слияние B и C--->A } E1, E2: boolean; Procedure SlianSer; { слияние серий из B и C ---> A } { S и T - первые элементы серий } { S.Key<0-весь файл B считан, T.Key<0-файл C считан } E1:=False; E2:=False; if (S.Key>0) and ((S.Key { файл B не считан и текущий элемент B меньше, чем в C либо файл C полностью считан } CopyElem(B, A, S, E1); if E1 then { достигнут конец серии на B } CopySer(C, A, T) CopyElem(C, A, T, E2); if E2 then { достигнут конец серии на C } CopySer(B, A, S) Begin { начало Slian } if not (Eof(B) or Eof(C)) then begin { оба файла не пусты } L:=0; { счетчик числа серий } While (S.Key>0) or (T.Key>0) do Begin { начало основной программы } Write("Введите имя файла для записи элементов: "); Assign(A, Name); Assign(B, "Rab1"); Assign(C, "Rab2"); L:=0; { L - число серий после слияния - параметр } WriteLn("Файл A: "); Pech(A); Raspred; { фаза распределения } WriteLn("Файл B: "); Pech(B); WriteLn("Файл C: "); Pech(C); ReadLn; { пауза } Slian { фаза слияния } Until L<=1; { L=0, если исходный файл отсортирован } WriteLn("Файл A в конце: "); Close(B); Erase(B); { удаление рабочих файлов } Close(C); Erase(C); Стоит обратить внимание на процедуру копирования элемента с ленты на ленту CopyElem. Реально в файл записывается элемент из оперативной памяти, оставшийся от предыдущего копирования, а в память читается следующий элемент данного файла. Это связано с необходимостью постоянной проверки конца серии. Приходится особо учитывать случай, когда конец серии совпадает с концом файла. При слиянии считается количество получившихся серий. Сортировка заканчивается, когда остается единственная серия. Эффективность сортировки можно повысить, используя многопутевое слияние, в котором распределение выполняется на k лент. Поскольку число серий на каждом проходе уменьшается в k раз, количество пересылок M пропорционально величине n log k n. Если общее число лент четное, то можно использовать однофазный метод слияния, распределяя серии с одной половины лент на другую. Платой за повышение эффективности многопутевого слияния являются, как всегда, увеличение сложности реализации и дополнительные затраты внешней памяти. На сколько может отличаться количество серий после разделения? На первый взгляд кажется, что не более, чем на одну, но это не так. Например, при распределении серий 17, 25, 41, ’ 9, 60, ‘ 50, 52, ‘ 7 первая и третья серии сливаются в общую серию, что не происходит со второй и четвертой сериями. В результате при последующем слиянии серии на одной из лент могут закончиться раньше, и придется впустую переписывать остаток другой ленты, теряя эффективность. Подобные ситуации учитываются в методе многофазной сортировки. Рассмотрим его на примере трех лент. Пусть при соединении лент B и C на ленту A серии на B заканчиваются раньше. Тогда лента B объявляется выходной, а лента A становится входной. Процесс продолжается до нового повторения ситуации, когда серии на одной из входных лент заканчиваются. Многофазная сортировка возможна и при многопутевом слиянии. Например, при использовании в сортировке k лент можно постоянно иметь одну выходную ленту. При исчерпании серий на одной из k-1 входных лент эта лента становится выходной вместо предыдущей выходной ленты. Методы внутренней и внешней сортировок могут использоваться совместно. Пусть сортируется большой по объему файл. В оперативной памяти выделяется буфер максимально возможного размера. Файл делится на блоки, соответствующие величине буфера. Блоки читаются в буфер, сортируются одним из методов внутренней сортировки и переписываются в другой файл. Сейчас каждый блок нового файла является серией достаточно большой длины, определяемой размером буфера. Остается применить один из методов внешней сортировки, использующий данные серии.Selection sort. Сортировка выбором
Начнем с самого простого и очевидного способа. Суть его нам отлично демонстрирует Роберт Седжвик в своей видеолекции на coursera (привожу погано пережатую в gif мной анимацию оттуда):
Пробегая по массиву с первого элемента, мы на каждом шаге ищем в правой части минимальный элемент, с которым и меняем местами текущий. В результате мы оставляем за собой окончательный вариант нашего массива в отсортированном виде.
Вот код, реализующий этот алгоритм на Java:
public
void
sort
(int
array)
{
int
n =
array.
length;
for
(int
i =
0
;
i <
n;
i ++
)
{
int
minIndex =
min
(array,
i,
n -
1
)
;
swap
(array,
i,
minIndex)
;
}
}
public
static
void
swap
(int
array,
int
i,
int
j)
{
int
temp =
array[
i]
;
array[
i]
=
array[
j]
;
array[
j]
=
temp;
}
public
static
int
min
(int
array,
int
begin,
int
end)
{
int
minVal =
array[
begin]
;
int
minIndex =
begin;
for
(int
i =
begin +
1
;
i <=
end;
i++
)
{
if
(array[
i]
<
minVal)
{
minVal =
array[
i]
;
minIndex =
i;
}
}
return
minIndex;
}
Анализ алгоритма показывает, что необходимо на каждом проходе прошерстить весть остаток массива, то есть нам понадобится ровно N + (N-1) + (N-2) + … + 1 = N^2/2 сравнений. Таким образом, сложность алгоритма составляет O(N^2). Что же это означает? А означает это, что, увеличив количество элементов в массиве (N) в 2 раза, мы увеличим время работы алгоритма не в 2, а в 2^2 = 4 раза. Увеличив N в 10 раз, время работы увеличим в 100 раз и так далее. На моем ноутбуке 2012 года с процессором Core i3 под Ubuntu 14.4 я получил следующее время работы:
Insertion sort. Сортировка вставками
Здесь идея несколько иная. Опять же, обратимся к анимации от Доктора Седжвика:
То, что впереди, нами еще даже не просмотрено, а все что оставляем позади себя, всегда остается выстроенным по порядку. Суть в том, что каждый новый элемент исходного массива мы «возвращаем» к началу до тех пор, пока он не «упрется» в меньший элемент.
Таким образом, у нас опять N проходов (для каждого элемента исходного массива), но в каждом проходе в большинстве случаев мы просматриваем не весь остаток, а только часть. То есть вариант 1 + (N-1) + (N-2) + … + N = N^2/2 мы получим, только если каждый следующий элемент нам придется возвращать к самому началу, то есть в случае отсортированного «наоборот» входного массива (не везет, так невезет). В случае же уже отсортированного массива (вот везуха ваще) будет полная халява – на каждом проходе всего одно сравнение и оставление элемента на месте, то есть отработает алгоритм за время, пропорциональное N. Сложность алгоритма же будет определяться худшим теоретическим случаем, то есть O(N^2). Среднестатистически же, время работы будет пропорционально N^2/4, то есть, вдвое быстрее предыдущего алгоритма. В моей реализации из-за неоптимального использования перестановки время работы получилось больше, чем у Selection. Планирую в ближайшее время исправить и обновить пост.
Вот код и результат его работы на той же машине:
public
void
sort
(int
array)
{
int
length =
array.
length;
for
(int
i =
1
;
i <
length;
i++
)
{
for
(int
j =
i;
j >=
1
;
j--
)
{
if
(array[
j]
<
array[
j -
1
]
)
swap
(array,
j,
j -
1
)
;
else
break
;
}
}
}
Shell sort. Сортировка Шелла
Умный мужик Дональд Шелл аж в 1959-м году заметил, что в алгоритме вставками дороже всего обходятся случаи, когда элемент возвращается очень далеко к началу массива: на каком-то проходе мы вернем элемент к началу на пару позиций, а на другом проходе почти через весь массив к началу – далеко и долго. Нельзя ли это сделать сразу, прыгая через несколько элементов? И такой способ он нашел. Заключается он в последовательном выполнении особых частичных сортировок, называемых в общем виде d-sort или, у Седжвика, h-sort (подозреваю, h означает hop - прыжок).
3-sort, например, будет сравнивать рассматриваемый элемент не с предыдущим, а пропустит два и сравнит с отстоящим на 3 позиции назад. Если поменяли, он его сравнит снова с элементом на 3 позиции назад и так далее.
Суть в том, что полученный в результате массив будет «3-отсортирован», то есть неправильность положения элементов составит менее 3х позиций. Работать с таким алгоритму вставки будет легко и приятно. Кстати, «1-sort» является ничем иным, как просто алгоритмом вставки=)
Последовательно применяя к массиву h-sort с уменьшающимся значением h, мы сможем отсортировать большой массив быстрее. Вот как это выглядит:
Сложность здесь заключается в том, как выбрать правильную последовательность частичных сортировок. От этого, в итоге, зависит производительность алгоритма. Наиболее распространенной является последовательность, предложенная Дональдом Кнутом:
h = h*3 + 1, то есть 1, 4, 13, 40, … и так до 1/3 размера массива. Такая последовательность обеспечивает достойную производительность, а также проста в реализации.
Анализ алгоритма требует тонн матана и мной не осилен. Обширность анализа так же определяется множеством вариантов последовательностей h. Эмпирически же можно сказать, что скорость алгоритма весьма хороша – смотрите сами:
Миллион элементов менее, чем за секунду!
А вот код на Java с кнутовской последовательностью.
public
void
sort
(int
array)
{
int
h =
1
;
while
(h*
3
<
array.
length)
h =
h *
3
+
1
;
while
(h >=
1
)
{
hSort
(array,
h)
;
h =
h/
3
;
}
}
private
void
hSort
(int
array,
int
h)
{
int
length =
array.
length;
for
(int
i =
h;
i <
length;
i++
)
{
for
(int
j =
i;
j >=
h;
j =
j -
h)
{
if
(array[
j]
<
array[
j -
h]
)
swap
(array,
j,
j -
h)
;
else
break
;
}
}
}
Bubble sort. Метод пузырька
Это классика! Этот алгоритм реализует почти каждый начинающий программист. Это настолько классика, что у Доктора Седжвика даже не нашлось анимации для него, потому мне пришлось потрудиться самому.
Здесь на каждом проходе мы обходим массив с начала до конца, меняя местами соседние элементы, стоящие не по порядку. В результате самые крупные элементы «всплывают» (отсюда и название) в конец массива. Каждый новый проход мы начинаем, оптимистично надеясь, что массив уже отсортирован (sorted = true). В конце прохода, если мы видим, что ошиблись, начинаем новый проход.
Сложность здесь заключается в том, что мы, опять же, обходим весь (почти) массив на каждом проходе. Сравнение происходит на каждом шаге, обмен - почти на каждом, что делает данный алгоритм одним из самых медленных (если рассматривать рационально реализованные, а не "сортировку встряхиванием" и прочие подобные).
Интересно, что формально сложность и здесь будет равна O(N^2), только вот коэффициент гораздо выше, чем у вставок и выборов. Код алгоритма:
public
void
sort
(int
array)
{
boolean
isSorted;
int
nMinusOne =
array.
length -
1
;
for
(int
i =
0
;
i <
nMinusOne;
i++
)
{
isSorted =
true
;
for
(int
j =
0
;
j <
nMinusOne -
i;
j++
)
{
if
(array[
j]
>
array[
j +
1
]
)
{
swap
(array,
j,
j +
1
)
;
isSorted =
false
;
}
}
if
(isSorted)
return
;
}
}
Время работы:
Почувствуйте разницу: более получаса на миллионе элементов!
Вывод: Никогда не исползуйте этот алгоритм!!!
Резюме первой части
Как итог предлагаю посмотреть общую таблицу для этих алгоритмов.
Можете так же сравнить с результатами для встроенного метода java.util.Arrays.sort() . Похоже на какую-то магию - что же может быть быстрее Шелла? Об этом напишу в следующей части. Там мы рассмотрим широко применяемые алгоритмы быстрой сортировки, а также сортировки слиянием, узнаем о разнице в методах сортировки массивов из примитивов и ссылочных типов, а также познакомимся с очень важным в этом деле интерфейсом Comparable ;)
Ниже можете изучить график, построенный в логарифмическом масштабе по данным таблицы. Чем более полого идет линия, тем лучше алгоритм =)
Кто хочет скачать весь проект и прогнать тесты у себя, держите ссылку:
Java
До встречи в следующей части! =)