Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

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

1. Классификация алгоритмов сортировки

Устойчивость (англ. stability) - устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.

Естественность поведения - эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(nЧlogn), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

Внешняя сортировка оперирует запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е. в данный момент мы «видим» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

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

- объём данных не позволяет им разместиться в ОЗУ.

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

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

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

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

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

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

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

Сортировка методом Шелла работает путём вставки отсортированных подмножеств основного списка. Каждое подмножество формируется за счёт выборки каждого n-ного элемента массива, начиная с любой позиции в списке. В результате будет получено n подмножеств, которые отсортированы методом вставок. Полученная последовательность элементов массива называется отсортированной по n. Затем значение n уменьшается и снова выполняется сортировка. Уменьшение значений n происходит до тех пор, пока n не будет равно 1, после чего последний проход будет представлять собой стандартную сортировку методом вставок.

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

Какие значения n лучше использовать?

Дональд Л. Шелл предложил значения 1, 2, 4, 8, 16, 32 и т.д. (естественно в обратном порядке), но с этими значениями связана одна проблема: до последнего прохода элементы массива с чётными индексами никогда не сравниваются с элементами нечётного индексами. И, следовательно, при выполнении последнего прохода всё ещё возможны перемещения элементов на большие расстояния.

В 1969 году Дональд Кнут (Donald Knuth) предложил последовательность 1, 4, 13, 40, 121 и т.д. (каждое последующее значение на единицу больше, чем утроенное предыдущее значение). Для массивов средних размеров эта последовательность позволяет получить достаточно высокие характеристики быстродействия.

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

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

Сортировка методом прочёсывания (comb sort) не относится к стандартным алгоритмам. На сегодняшний день он малоизвестен, тем не менее, он отличается достаточно быстрым уровнем быстродействия и удобной реализацией. Метод был разработан Стефаном Лейси (Stephan Lacey) и Ричардом Боксом (Richard Box) в 1991 году. Фактически он использует пузырьковую сортировку таким же образом, как и сортировка, методом Шелла сортировку методом вставок.

Табл. 7

Перетасуйте карты и разложите на столе. Выделите 1 и 9 карту (расстояние между картами 8), если они находятся в неправильном порядке - поменяйте их местами. Выделите 2 и 10 карты (расстояние между картами 6) и, при необходимости, поменяйте их местами. То же самое проделайте для 3 и 11 карты (расстояние между картами 4), 4 и 12 карты (расстояние между картами 3), а затем 5 и 13 (расстояние между картами 2). Далее сравнивайте и переставляйте пары карт (1, 7), (2, 8), (3, 9), (4, 10), (5, 11), (6, 12) и (7, 13), т.е. карты отстоящие друг от друга на шесть позиций. А теперь выполните проход по разложенным картам, отстоящим друг от друга на четыре позиции, затем на три и две позиции, как показано на рисунке 6. После этого выполните стандартную пузырьковую сортировку.

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

Каким образом были получены значения расстояний 8, 6, 4 ,3, 2, 1? Разработчики этого метода сортировки провели большое количество экспериментов и эмпирическим путём пришли к выводу, что значение каждого последующего расстояния «прыжка» должно быть получено в результате деления предыдущего значения расстояния на 1,3.

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

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

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