Методы сортировки массивов

1. Алгоритмы устойчивой сортировки (самые медленные алгоритмы сортировки, принадлежащие к классу О (n2)):

Пузырьковая сортировка (метод простых обменов).

Шейкер-сортировка.

Сортировка методом выбора (метод простого выбора).

Сортировка методом вставок.

Сортировка парным (бинарным) деревом.

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

Методы пузырьковой сортировки, шейкер-сортировки, сортировки выбором и сортировки вставок с целью упрощения понимания будут описаны на примере сортировки колоды карт. Для этого выберем все карты одной масти из колоды, например черви, и перетасуем их (манипулирование только 13 картами позволит упростить нашу работу, сделав её более наглядной). Более подробное описание данных методов изложено в книге Джулиан М. Бакнелла: «Фундаментальные алгоритмы и структуры данных в Delphi».

Пузырьковая сортировка (метод простых обменов).

Первый алгоритм, с которыми сталкиваются все программисты при изучении азов программирования, — это пузырьковая сортировка (bubble sort).

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

Табл. 1.

Пузырьковая сортировка работает следующим образом. Разложите ваши карты (помните, их всего 13). Посмотрите на двенадцатую и тринадцатую карту. Если двенадцатая карта старше тринадцатой, поменяйте их местами. То же сделайте и для пар (10, 11), (9, 10), и т. д., пока не дойдетё до первой и второй карты. После первого прохода по всей колоде туз окажется на первой позиции. Фактически когда вы «зацепились» за туз он «выплыл» на первую позицию, как показано на рисунке 1. Продолжайте процесс сортировки, уменьшая с каждым новым циклом количество просматриваемых карт и поступая так до тех пор, пока вся колода не будет отсортирована.

Идея метода: Весь массив рассматривается несколько раз, причем при каждом рассмотрении сравниваются значения 2-х соседних элементов. Если они стоят в неправильном порядке, то производится их перестановка. Так происходит до тех пор, пока не будет выполнено ни одной перестановки. Метод называют пузырьковой сортировкой, потому что меньшие значения элементов постепенно «всплывают», как пузырьки воздуха в воде, перемещаясь в начало массива, а «тяжелые» элементы «оседают на дно» .

Полагаю, вы согласитесь с тем, что сортировка была довольно утомительной. При реализации алгоритма на языке Паскаль «утомительность» выражается медленной скоростью работы. Тем не менее, существует один простой метод описания пузырьковой сортировки: если при выполнении очередного прохода не было выполнено ни одной перестановки, значит, карты уже отсортированы в требуемом порядке.

Пузырьковая сортировка принадлежит к алгоритмам класса О (n2). Как видите в реализации присутствуют два цикла: внешний и внутренний. Количество выполнений каждого цикла зависит от количества элементов в массиве — n. При первом выполнении внутреннего алгоритма будет произведено n-1 сравнений, при втором n-2, при третьем n-3 и т. д. Всего будет n-1 таких циклов, таким образом общее количество сравнений составит:

(n-1) + (n-2) + … + 1.

Приведённую сумму можно упростить до n (n-1)/2 или (n2- n)/2. Другими словами, получаем О (n2). Количество перестановок вычислить несколько сложнее, но в худшем варианте (если элементы в исходном наборе были отсортированы в обратном порядке) количество перестановок будет равно количеству сравнений, т. е. получаем О (n2).

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

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

Шейкер-сортировка Пузырьковая сортировка имеет одну вариацию, которая на практике даёт незначительное увеличение скорости, — это так называемая шейкер-сортировка (shake sort).

Вернёмся к картам. Выполним первый проход согласно алгоритму сортировки, как показано в табл. 2. Туз попадает на первую позицию.

Табл. 2.

Табл. 3.

Теперь, вместо прохода колоды карт справа налево, пройдите слева направо: сравните вторую и третью карты и старшую карту поместите на третью позицию. Сравните третью и четвёртую карты, и при необходимости поменяйте их местами. Продолжайте сравнения вплоть до достижения пары (12, 13). По пути к правому краю колоды вы «захватили» короля и переместили его на последнюю позицию.

А теперь снова пройдите колоду справа налево до второй карты. Во вторую позицию попадёт двойка. Продолжайте чередовать направления проходов до тех пор, пока не будет отсортирована вся колода.

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

Как и пузырьковая сортировка, шейкер-сортировка относится к неустойчивым алгоритмам.

Сортировка методом выбора (метод простого выбора) Сортировка методом выбора (selection sort).

Табл. 4.

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

Сортировка методом выбора относится к алгоритмам класса О (n2). Количество выполняемых сравнений для первого прохода равно n, для второго n-1 и т. д. общее количество сравнений будет равно n (n+1)/2−1, т. е. сортировка принадлежит к классу О (n2). Тем не менее, количество перестановок намного меньше: при каждом выполнении внешнего цикла производится всего одна перестановка. Таким образом, общее количество перестановок (n-1), т. е. О (n). Что это означает на практике? Если время и требуемые ресурсы перестановки элементов массива намного больше, чем время сравнения, то сортировка методом выбора оказывается достаточно эффективной.

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

Идея метода: весь массив просматривается несколько раз и на каждом шаге ищется минимальный элемент и запоминается его порядковый номер. Затем найденный минимальный элемент меняется значением с первым, вторым, третьим и т. д. предпоследним элементом массива и исключается из рассмотрения.

Сортировка методом вставок Сортировка методом вставок или сортировка простыми вставками (insertion sort). Рассмотрим принцип действия данного алгоритма на той же колоде карт.

Табл. 5.

Начинаем с левого края колоды. Сравниваем две первые карты и располагаем их в правильном порядке. Смотрим на третью карту. Вставляем её в требуемое место по отношению к первым двум картам. Смотрим на четвёртую карту и вставляем её в требуемое место по отношению к первым трём картам. Те же операции выполняем с последующими картами. При перемещении слева направо часть колоды будет отсортирована, как показано в табл. 5.

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

Идея метода: делается предположение, что первый n элемент массива уже упорядочен и рассматривается n+1 элемент. Если окажется, что он меньше чем какой либо из первых n, то он занимает место большего, а участок массива ограниченный его новым местом и старым смещается вправо.

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

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

Как и при пузырьковой сортировке, при сортировке методом вставок элементы массива попадают в нужные позиции только за счёт смены позиций с соседними элементами. Если элемент находится далеко от требуемой позиции, его перемещение занимает много времени.

Сортировка двоичным (бинарным) деревом.

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

Описание метода сортировки двоичным деревом детально рассмотрено в книге Н. Вирта: «Алгоритмы и структуры данных».

Вместо «предшественник» и «преемник» также употребляют термины «родитель» и «сын». Все элементы дерева также называют «узлами». При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом, вставляя на место. Если элемент >= корня — он идет в правое поддерево, сравниваем его уже с правым сыном, иначе — он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить.

Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:

44 44 44 44 44.

/ / /.

55 12 55 12 55 12 55.

• 42 42 94
• (**) 44 44 (*) 44

/ / /.

12 55 12 55 12 55.

/ /.

42 94 06 42 94 06 42 94.

/ / / /.

18 18 18 67.

Дерево может быть и более-менее ровным, как на (*), может и иметь всего две основные ветви (**), а если входная последовательность уже отсортирована, то дерево выродится в линейный список.

Если мы будем рекурсивно обходить дерево по правилу «левый сын — родитель — правый сын», то, записывая все встречающиеся элементы в массив, мы получим упорядоченное в порядке возрастания множество. Hа этом и основана идея сортировки деревом.

Более подробно правило обхода можно сформулировать, как обойти левое поддерево — вывести корень — обойти правое поддерево, где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.

Общее быстродействие метода O (nЧlogn). Поведение неестественно, устойчивости, вообще говоря, нет.

Основной недостаток этого метода — большие требования к памяти под дерево. Очевидно, нужно n места под ключи и, кроме того, память на 2 указателя для каждого из них.

Поэтому данная сортировка обычно применяют там, где:

• — построенное дерево можно с успехом применить для других задач;
• — данные уже построены в 'дерево';
• — данные можно считывать непосредственно в дерево.

Так как не тратится лишняя память, например, при потоковом вводе с консоли или из файла.

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

Сортировка слиянием (merge sort) привлекает своей простотой и наличием некоторых особенностей (например, она принадлежит к алгоритмам класса O (nЧlog (n)) и не имеет худших случаев), но если приступить к его реализации, можно натолкнуться на большую проблему. Тем не менее, сортировка слиянием очень широко используется при необходимости сортировки содержимого файлов, размер которых слишком велик, чтобы поместиться в памяти. Данный метод также рассмотрен в книге Джулиан М. Бакнелла: «Фундаментальные алгоритмы и структуры данных в Delphi».

В качестве примера мы не будем пользоваться картами — алгоритм легко понять и без карт.

Представьте себе, что имеется два уже отсортированных массива и необходимо сформировать один массив, объединяющий в себе все элементы исходных массивов. Путь № 1 состоит в том, чтобы скопировать оба массива в результирующий и выполнить его сортировку. но в этом случае, к сожалению, мы не воспользуемся тем, что исходные массивы уже отсортированы. Путь № 2 предусматривает слияние.

Смотрим на первые элементы обоих массивов. Элемент с меньшим значением переносим в результирующий массив. Снова смотрим на первые элементы в обоих массивах и снова переносим в результирующий массив элемент с меньшим значением, удаляя его из исходного массива. описанный процесс продолжается до тех пор, пока не исчёрпываются элементы одного из исходных массивов. После этого в результирующий массив можно перенести все оставшиеся элементы в исходном массиве. Такой алгоритм формально известен под названием алгоритма двухпутевого слияния (two-way merge algorithm).

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

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

Так каким же образом алгоритм двухпутевого слияния помогает выполнить сортировку? Ведь для его работы необходимо иметь два отсортированных массива меньшей длины, из которых создаётся один большой массив.

На основе такого описания можно придти к рекурсивному определению сортировки слиянием: разделите исходный массив на две половины, примените к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма слияния объедините подписки в один отсортированный массив.

Сортировка слиянием обладает только одним недостатком — алгоритм слияния требует наличия третьего массива, в котором будут храниться результаты слияния.

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

Что касается устойчивости, то поскольку элементы массива перемещаются только при процедуре слияния, устойчивость всей сортировки слиянием будет зависеть от устойчивости самого слияния двух половин массива. Если в обеих половинах исходного массива имеются элементы с одинаковым значением, то оператор сравнения гарантирует, что первым в результирующий список попадёт элемент из первой половины исходного массива. Это означает, что операция слиянием сохраняет относительный порядок элементов, и, следовательно, сортировка слиянием будет устойчивой.

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

Несмотря на то, что сортировка слиянием требует дополнительной памяти (объём которой пропорционален количеству элементов в исходном массиве), она обладает некоторыми интересными свойствами:

• — сортировка слиянием принадлежит к классу O (nЧlog (n)).
• — она устойчива.
• — для сортировки слиянием не имеет значения ни порядок элементов в исходном массиве (будь то массив, отсортированный в прямом порядке или обратном), ни повторения значений в массиве, то есть сортировка слиянием не имеет худшего случая.

Очевидно, требуется n операций на создание первоначального дерева, а затем n шагов, каждый по logn сравнений для выбора нового наименьшего.

2. Алгоритмы неустойчивой сортировки:

Сортировка методом Шелла.

Сортировка методом прочёсывания.

Пирамидальная сортировка (сортировка деревом).

Быстрая сортировка.

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

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

Более подробное описание сортировки методом Шелла, сортировки методом прочёсывания и быстрой сортировки также изложено в книге Джулиан М. Бакнелла: «Фундаментальные алгоритмы и структуры данных в Delphi».

Сортировка методом Шелла.

Этот метод разработал Дональд Л. Шелл в 1959 году. Он основан на сортировке методом вставок.

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

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

После первого прохода карты будут находиться в отсортированном порядке по 4, какую бы карту не выбрали, карты, которые находятся на количество позиций, кратном 4 вперёд и назад, будут отсортированы в требуемом порядке.

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

массив сортирующий алгоритм бинарный Табл. 6.