Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Классификация алгоритмов сортировки).pdf

Как мы упоминали ранее, это дополнительное свойство (устойчивость) означает, что, как правило, характеристики по быстродействию и потребляемой памяти у алгоритмов устойчивой сортировки будут хуже, чем при использовании неустойчивой сортировки. Опишем ниже чаще всего используемые методы устойчивой сортировки, с указанием порядка их скорости и потребляемой памяти:

• Сортировка пузырьком (скорость , память );
• Сортировка перемешиванием (скорость , память );
• Сортировка вставками (скорость , память );
• Сортировка слиянием (скорость , память );
• Метод TimSort (скорость , память ).

Как можно видеть, лишь два метода устойчивой сортировки имеют асимптотическую скорость в , однако они требуют дополнительного объема памяти. Те же алгоритмы, которые не требуют дополнительной памяти, имеют асимптотическую скорость . Это связано с тем, что нам необходимо обеспечивать дополнительное свойство устойчивости.

Рассмотрим каждый из этих алгоритмов более подробно:

4.1 Сортировка пузырьком

Алгоритм сортировки пузырьком (или пузырьковой сортировки) состоит в повторяющихся проходах по массиву. Если размер массива, который необходимо отсортировать составляет элементов, то по массиву необходимо пройти раз.

Во время каждого такого прохода производится сравнение двух расположенных рядом элементов массива – первого и второго, второго и третьего, третьего и четвертого, и так далее. Если выясняется, что элементы массива расположены неверно (например, второй элемент больше третьего, а мы пытаемся упорядочить массив по возрастанию), то мы меняем их местами.

За один проход массива самый «тяжелый» элемент массива становится последним – ведь при его встрече он сразу же будет обменян местами с соседом, затем снова и снова, пока не сдвинется в самый конец массива. С другой стороны, более легкие элементы массива сдвинутся ближе к началу, и с каждым проходом будут сдвигаться все дальше и дальше, пока, наконец, не займут свое место. Именно из-за такого постепенного сдвига («всплывания») более легких элементов сортировка была названа пузырьковой – легкие элементы, как пузырьки, постепенно всплывают наверх, в то время как тяжелые элементы падают вниз.

Легко видеть, что максимум после проходов массив окажется отсортирован. Однако количество необходимых проходов может быть различным. Вполне может быть, что массив и так практически отсортирован, и хватит одного прохода. Таким образом, данный алгоритм можно немного «ускорить», на каждом проходе запоминая, произошел ли хоть один обмен или нет. Если мы совершили проход по массиву, но не поменяли ни одной пары ячеек друг с другом, то алгоритм можно заканчивать, не дожидаясь полного числа () проходов.

Алгоритм сортировки пузырьком – простейший для понимания, наряду с сортировкой выбором. Именно поэтому его используют в учебных целях, однако в реальных высоконагруженных и сложных проектах встретить его довольно непросто, хотя и там его можно использовать, если размер сортируемого массива достаточно невелик (до ста элементов).

4.2 Сортировка перемешиванием

Сортировка перемешиванием является дальнейшим улучшением рассмотренной ранее пузырьковой сортировки. Легко заметить, что при использовании пузырьковой сортировки можно не доходить каждый раз до конца сортируемого массива. Если у нас был массив длины , и мы осуществили по нему проход пузырьковой сортировки, однако заметили, что уже после элемента ни одного обмена не было сделано, то можно сказать, что их не будет сделано никогда (ранее мы разобрались, что самые «тяжелые» элементы в пузырьковой сортировке сразу же попадают в конец массива, и затем уже не сдвигаются). Следовательно, при очередном шаге сортировки мы можем доходить уже не до конца исходного массива, а до некоторого элемента , который изменялся на предыдущем шаге последним.

Однако таким образом мы сможем улучшить пузырьковую сортировку лишь с одной стороны – конечной. Каждый раз мы будем доходить не до конца массива, а до некоторого элемента, все ближе стоящего к началу. Поэтому в сортировке перемешиванием используется и вторая оптимизация – после того, как мы провели один проход пузырьковой сортировки от начала массива до конца, мы начинаем двигаться в обратном направлении, от конца к началу, и сортируем в обратном порядке (если исходный массив мы сортировали в порядке возрастания, то в обратную сторону мы начинаем сортировать его в порядке убывания). Таким образом, снова применяя первую оптимизацию, в следующий раз мы сможем сортировать массив уже не от начала (первого элемента), а от какого-то элемента, стоящего после первого (на котором произойдет последний обмен при проходе пузырьковой сортировки в обратную сторону).

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

4.3 Сортировка вставками

В методе сортировки вставками вместо того, чтобы каждый раз просматривать конкретные пары элементов, мы берем лишь один элемент (сначала первый, затем второй, затем третий, и т.д.) Каждый элемент мы сдвигаем влево, до тех пор, пока он не окажется на своем месте среди уже отсортированной области.

Можно заметить, когда мы просмотрели и расположили на нужном месте элемент массива с номером , весь массив с первого до -ого элемента (если не учитывать элементы, начиная с до конца массива) уже отсортирован. Действительно, когда мы берем первый элемент, он отсортирован по умолчанию (массив из одного элемента). Если второй элемент больше чем первый, то мы просто возьмем его, и никуда не переместим. Если же он окажется меньше первого, то мы сдвинем его влево, пока он не окажется на своем месте (то есть, на первом). В любом случае, первые два элемента окажутся отсортированы. Когда мы возьмем третий элемент, мы точно также расположим его на своем месте среди первых двух (на первом, втором или третьем месте). В итоге, у нас окажется массив из трех отсортированных элементов. Повторяя данный процесс, мы придем к тому, что отсортированным окажется весь исходный массив.

Отобразим действие данного вида сортировки на примере. Допустим, у нас есть массив из четырех элементов 1-5-3-2. Попробуем его отсортировать.

• Шаг №1. Работаем с первым элементом массива «1». Так как других элементов пока нет, оставим его на своем месте;
• Шаг №2. Работаем со вторым элементом массива «5». Он больше чем уже отсортированный массив «1», поэтому также оставим его на своем месте;
• Шаг №3. Работаем с третьим элементом массива «3». Он меньше, чем последний элемент уже отсортированного массива «1-5», поэтому сдвигаем его влево. Теперь первые три элемента массива «1-3-5»:
• Все еще работаем с третьим (теперь уже вторым) элементом массива «3». Это значение больше чем следующее в отсортированном
  массиве – «1», поэтому оставляем его на своем месте;
• Шаг №4. Работаем с четвертым элементом массива «2». Он меньше, чем последний элемент уже отсортированного массива «1-3-5», поэтому сдвигаем его влево. Теперь первые четыре элемента массива «1-3-2-5»:
• Все еще работаем с четвертым (теперь уже третьим) элементом массива «2». Это значение все еще больше чем следующее в отсортированном массиве – «3», поэтому снова сдвигаем его влево. Теперь первые четыре элемента массива «1-2-3-5»;
• Все еще работаем с четвертым (теперь уже вторым) элементом массива «2». Это значение больше чем следующее в отсортированном
  массиве – «1», поэтому оставляем его на своем месте.
• Мы взяли все элементы с первого до четвертого, поэтому массив отсортирован. Действительно, «1-2-3-5» это числа, расположенные по возрастанию.

Данный алгоритм тоже имеет асимптотическое время выполнения . Такое время получается потому, что мы должны сделать какую-то работу для каждого элемента массива. Таких элементов , следовательно, это займет по времени . С другой стороны, для каждого такого элемента нужно сдвинуть его влево на какое-то число шагов. Это число тем больше, чем больше элементов в нашем массиве (максимально мы можем сдвинуть его на элементов), что также дает по времени . Итого мы получаем время выполнения в .

Из-за довольно медленного выполнения сортировки данный алгоритм редко используется на практике. Однако его довольно просто объяснить, поэтому вполне допустимо его использование в учебных целях.

4.4 Сортировка слиянием

Сортировка слиянием – это самый простой алгоритм сортировки, обладающий свойством устойчивости, который при этом имеет скорость порядка . Рассмотрим данный алгоритм, чтобы понять, за счет чего достигается такое увеличение скорости по сравнению с другими устойчивыми алгоритмами сортировки.

При использовании сортировки слиянием массив делится на две части примерно одинакового размера (соответственно, лучше всего, если массив будет иметь длину равную степени двойки – тогда его можно будет делить на две части вплоть до одного элемента). Далее каждая половина сортируется каким-либо алгоритмом, чаще всего рекурсивным вызовом самой процедуры сортировки слиянием. В результате мы получаем две отсортированных половины массива. Эти половины массива затем, на последнем шаге, объединяются в один итоговый массив. Это можно сделать достаточно быстро (со скоростью ), просто объявив указатели на первые элементы каждой из половинок, и последовательно беря числа из нужной половины, одновременно сдвигая указатели.

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

Рассмотрим реализацию данного алгоритма на примере. Допустим, у нас есть массив из восьми (степень двойки) элементов, равных
«6-5-3-1-8-7-2-4». Необходимо отсортировать данный массив по возрастанию.

Шаг №1. Делим данную последовательность на две равных
части – «6-5-3-1» и «8-7-2-4». Вызываем для первой части «6-5-3-1» ту же процедуру сортировки.

Шаг №1.1. Делим данную нам последовательность «6-5-3-1» на две равных части – «6-5» и «3-1». Вызываем для первой части «6-5» ту же процедуру сортировки;

Шаг №1.1.1. Так как в переданной нам последовательности всего два члена - «6-5», сравним их, и обменяем местами – «5-6»;

Шаг №1.2. Вызовем для второй части «3-1» ту же процедуру сортировки;

Шаг №1.2.1. Так как в переданной нам последовательности всего два члена - «3-1», сравним их, и обменяем местами – «1-3»;

Шаг №1.3. Мы получили две отсортированных последовательности – «5-6» и «1-3». Объединим их в одну последовательность. Поставим указатели на первые элементы каждой из последовательностей – «5» и «1». Сравним их. Очевидно, что 1 меньше, чем 5, поэтому возьмем элемент «1» из второй последовательности. Сдвинем указатель. Теперь у нас две последовательности – «5-6» и «3», и результирующий массив «1». Точно также добавим остальные элементы в порядке возрастания, и получим массив «1-3-5-6»;

Шаг №2. Вызовем для второй части «8-7-2-4» ту же процедуру сортировки;

Шаг №2.1. Делим данную нам последовательность «8-7-2-4» на две равных части – «8-7» и «2-4». Вызываем для первой части «8-7» ту же процедуру сортировки;

Шаг №2.1.1. Так как в переданной нам последовательности всего два члена - «8-7», сравним их, и обменяем местами – «7-8»;

Шаг №2.2. Вызовем для второй части «2-4» ту же процедуру сортировки;

Шаг №2.2.1. Так как в переданной нам последовательности всего два члена - «2-4», сравним их. Они находятся в нужном порядке, поэтому не будем их трогать;

Шаг №2.3. Мы получили две отсортированных последовательности – «7-8» и «2-4». Объединим их в одну последовательность, как и ранее, используя указатели. В итоге получим массив «2-4-7-8»;

Шаг №3. Мы получили две отсортированных
последовательности – «1-3-5-6» и «2-4-7-8». Объединим их в одну последовательность, как и ранее, используя указатели. В итоге получим массив «1-2-3-4-5-6-7-8». Массив отсортирован.

Как можно видеть, сортировка слиянием действительно позволяет отсортировать массив, причем делает это гораздо быстрее (асимптотически), чем сортировки пузырька, или вставки. Из-за этого данная сортировка используется в реальных программных продуктах, например, в базе данных MySQL для реализации сортировки (при указании ORDER BY в запросе и отсутствии необходимых индексов).