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

Содержание:

Введение

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

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

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

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

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

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

• доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
• объём данных не позволяет им разместиться в ОЗУ.

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

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

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

Курсовая работа состоит из введения, двух глав, заключения и списка литературы.

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

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

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

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

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

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

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

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

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

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

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

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

Номинальное значение карты
5	Король	4	2	Валет	Туз	9	8	3	10	Дама	6	7
5	Король	4	2	Валет	Туз	9	8	3	10	Дама	6	7
5	Король	4	2	Валет	Туз	9	8	3	10	6	Дама	7
5	Король	4	2	Валет	Туз	9	8	3	6	10	Дама	7
5	Король	4	2	Валет	Туз	9	8	3	6	10	Дама	7
5	Король	4	2	Валет	Туз	9	3	8	6	10	Дама	7
5	Король	4	2	Валет	Туз	3	9	8	6	10	Дама	7
5	Король	4	2	Валет	Туз	3	9	8	6	10	Дама	7
5	Король	4	2	Туз	Валет	3	9	8	6	10	Дама	7
5	Король	4	Туз	2	Валет	3	9	8	6	10	Дама	7
5	Король	Туз	4	2	Валет	3	9	8	6	10	Дама	7
5	Туз	Король	4	2	Валет	3	9	8	6	10	Дама	7
Туз	5	Король	4	2	Валет	3	9	8	6	10	Дама	7

Рис. 1. Один проход с помощью алгоритма пузырьковой сортировки

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

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

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

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

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

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

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

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

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

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

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

Номинальное значение карты
5	Король	4	2	Валет	Туз	9	8	3	10	Дама	6	7
5	Король	4	2	Валет	Туз	9	8	3	10	Дама	6	7
5	Король	4	2	Валет	Туз	9	8	3	10	6	Дама	7
5	Король	4	2	Валет	Туз	9	8	3	6	10	Дама	7
5	Король	4	2	Валет	Туз	9	8	3	6	10	Дама	7
5	Король	4	2	Валет	Туз	9	3	8	6	10	Дама	7
5	Король	4	2	Валет	Туз	3	9	8	6	10	Дама	7
5	Король	4	2	Валет	Туз	3	9	8	6	10	Дама	7
5	Король	4	2	Туз	Валет	3	9	8	6	10	Дама	7
5	Король	4	Туз	2	Валет	3	9	8	6	10	Дама	7
5	Король	Туз	4	2	Валет	3	9	8	6	10	Дама	7
5	Туз	Король	4	2	Валет	3	9	8	6	10	Дама	7
Туз	5	Король	4	2	Валет	3	9	8	6	10	Дама	7

Рис. 2.1. Выполнение первого прохода с помощью шейкер-сортировки

Номинальное значение карты
Туз	5	Ко роль	4	2	Валет	3	9	8	6	10	Дама	7
Туз	5	Ко роль	4	2	Валет	3	9	8	6	10	Дама	7
Туз	5	4	Ко роль	2	Валет	3	9	8	6	10	Дама	7
Туз	5	4	2	Ко роль	Валет	3	9	8	6	10	Дама	7
Туз	5	4	2	Валет	Ко роль	3	9	8	6	10	Дама	7
Туз	5	4	2	Валет	3	Ко роль	9	8	6	10	Дама	7
Туз	5	4	2	Валет	3	9	Ко роль	8	6	10	Дама	7
Туз	5	4	2	Валет	3	9	8	Ко роль	6	10	Дама	7
Туз	5	4	2	Валет	3	9	8	6	Ко роль	10	Дама	7
Туз	5	4	2	Валет	3	9	8	6	10	Ко роль	Дама	7
Туз	5	4	2	Валет	3	9	8	6	10	Дама	Ко роль	7
Туз	5	4	2	Валет	3	9	8	6	10	Дама	7	Ко роль

Рис. 2.2. Выполнение второго прохода с помощью шейкер-сортировки

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

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

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

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

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

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

Номинальное значение карты
5	Король	4	4	Валет	Туз	9	8	3	10	Дама	6	7
Туз	Король	4	2	Валет	5	9	8	3	10	Дама	6	7
Туз	2	4	Король	Валет	5	9	8	3	10	Дама	6	7
Туз	2	3	Король	Валет	5	9	8	4	10	Дама	6	7
Туз	2	3	4	Валет	5	9	8	Король	10	Дама	6	7
Туз	2	3	4	5	Валет	9	8	Король	10	Дама	6	7
Туз	2	3	4	5	6	9	8	Король	10	Дама	Валет	7
Туз	2	3	4	5	6	7	8	Король	10	Дама	Валет	9
Туз	2	3	4	5	6	7	8	9	10	Дама	Валет	Король
Туз	2	3	4	5	6		8	9	10	Валет	Дама	Король

Рис. 3. Сортировка методом выбора

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

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

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

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

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

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

Номинальное значение карты
5	Ко роль	4	2	Валет	Туз	9	8	3	10	Дама	6	7
4	5	Ко роль	2	Валет	Туз	9	8	3	10	Дама	6	7
2	4	5	Ко роль	Валет	Туз	9	8	3	10	Дама	6	7
2	4	5	Валет	Ко роль	Туз	9	8	3	10	Дама	6	7
Туз	2	4	5	Валет	Ко роль	9	8	3	10	Дама	6	7
Туз	2	4	5	9	Валет	Ко роль	8	3	10	Дама	6	7
Туз	2	4	5	8	9	Валет	Ко роль	3	10	Дама	6	7
Туз	2	3	4	5	8	9	Валет	Ко роль	10	Дама	6	7
Туз	2	3	4	5	8	9	10	Валет	Ко роль	Дама	6	7
Туз	2	3	4	5	8	9	10	Валет	Дама	Ко роль	6	7
Туз	2	3	4	5	6	8	9	10	Валет	Дама	Ко роль	7
Туз	2	3	4	5	6	7	8	9	10	Валет	Дама	Ко роль

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

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

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

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

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

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

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

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

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

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

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

Вот процесс построения дерева из последовательности 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 указателя для каждого из них.

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

- построенное дерево можно с успехом применить для других задач;

- данные уже построены в 'дерево';

- данные можно считывать непосредственно в дерево.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Номинальное значение карты
5	Король	4	2	Валет	Туз	9	8	3	10	Дама	6	7
3	Король	4	2	5	Туз	9	8	7	10	Дама	6	Валет
3	Туз	4	2	5	10	9	8	7	Король	Дама	6	Валет
3	Туз	4	2	5	10	9	8	7	Король	Дама	6	Валет
3	Туз	4	2	5	10	9	6	7	Король	Дама	8	Валет
Туз	3	4	2	5	10	9	6	7	Король	Дама	8	Валет
Туз	2	3	4	5	10	9	6	7	Король	Дама	8	Валет
Туз	2	3	4	5	9	10	6	7	Король	Дама	8	Валет
Туз	2	3	4	5	6	9	10	7	Король	Дама	8	Валет
Туз	2	3	4	5	6	7	9	10	Король	Дама	8	Валет
Туз	2	3	4	5	6	7	9	10	Король	Дама	8	Валет
Туз	2	3	4	5	6	7	9	10	Дама	Король	8	Валет
Туз	2	3	4	5	6	7	8	9	10	Дама	Король	Валет
Туз	2	3	4	5	6	7	8	9	10	Валет	Дама	Король

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

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

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

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

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

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

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

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

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

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

Номинальное значение карты
5	Король	4	2	Валет	Туз	9	8	3	10	Дама	6	7
3	Король	4	2	Валет	Туз	9	8	5	10	Дама	6	7
3	10	2	4	Валет	Туз	9	8	5	Король	Дама	6	7
3	10	4	2	7	Туз	9	8	5	Король	Дама	6	Валет
3	8	4	2	7	Туз	9	10	5	Король	Дама	6	Валет
3	Туз	4	2	7	8	9	10	5	Король	Дама	6	Валет
3	Туз	4	2	5	8	9	6	7	Король	Дама	10	Валет
2	Туз	4	3	5	8	9	6	7	Король	Дама	10	Валет
2	Туз	4	3	5	7	9	6	8	Король	Дама	10	Валет
2	Туз	4	3	5	7	9	6	8	Валет	Дама	10	Король
2	Туз	4	3	5	6	9	7	8	Валет	Дама	10	Король
2	Туз	4	3	5	6	8	7	9	Валет	Дама	10	Король
2	Туз	4	3	5	6	8	7	9	10	Дама	Валет	Король
Туз	2	4	3	5	6	8	7	9	10	Дама	Валет	Король
Туз	2	3	4	5	6	8	7	9	10	Дама	Валет	Король
Туз	2	3	4	5	6	7	8	9	10	Дама	Валет	Король
Туз	2	3	4	5	6	7	8	9	10	Дама	Валет	Король

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

Перетасуйте карты и разложите на столе. Выделите 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. После этого выполните стандартную пузырьковую сортировку.^[6]

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

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

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

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

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

Метод пирамидальной сортировки более подробно изложен в книге Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайн: «Алгоритмы: построение и анализ, 2-издание» и в учебном пособии для студентов вузов Л.Г. Гагариной и В.Д. Колдаева «Алгоритмы и структуры данных».

Метод сортирующего дерева основан на повторяющихся поисках наименьшего значения среди n элементов массива, среди оставшихся n-1 элементов и т.д. Например, сделав n/2 сравнений, можно определить в каждой паре значений меньшее значение. С помощью n/4 сравнений — меньшее значение из пары уже выбранных меньших и т. д. Проделав n - 1 сравнений, мы можем построить дерево выбора, вроде представленного на рисунке 7.1 и идентифицировать его корень как нужное нам наименьшее значение.

06

06

06

06

12

12

12

44

44

55

42

94

18

18

67

Рис. 7.1. Повторяющиеся выборы среди двух значений

Второй этап сортировки — спуск вдоль пути, отмеченного наи­меньшим элементом, и исключение его из дерева путем замены на пустой элемент (дырку), как показано на рисунке 7.2. ^[7]

12

12

12

44

44

55

42

94

18

18

67

Рис. 7.2. Исключение наименьшего значения

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

12

18

67

12

12

12

44

44

55

42

94

18

18

67

Рис.7.3. Сдвигание элементов и заполнение пустых элементов (дырок)

Обратите внимание - на каждом из n шагов выбора требуется только log₂ n сравнений. Поэтому на весь процесс понадобится порядка n×log₂ n эле­ментарных операций плюс еще n шагов на построение дерева. Естественно, сохранение дополнительной информации делает за­дачу более изощренной, поэтому в сортировке по дереву увеличилась сложность отдельных шагов. Ведь для сохране­ния избыточной информации, получаемой при начальном прохо­де, создается некоторая древообразная структура.

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

Пирамида определяется как последовательность ключей h_l, h_l+1,...,h_r, такая, что hi <= h_2i. и hi< =h_2i+1, для i =l,..., r/2.

Если любое двоичное дерево рассматривать как массив, представленный на рисунке 7.4, то можно говорить, что деревья сортировок, представленными на рисунках 7.5 и 7.6 являются пирамидами, а элемент h_l её наименьший элемент: h_l = min(h₁, h₂,…, h_n).

h₁

h₃

h₇

h₂

h₅

h₁₀

h₄

h₈

h₉

h₁₁

h₁₂

h₆

h₁₃

h₁₅

h₁₄

Рис. 7.4. Массив h, представленный в виде двоичного дерева

h₁

06

12

42

94

55

18

Рис.7.5. Пирамида из семи элементов.

Предположим, есть некоторая пи­рамида с заданными элементами hi,.., hr. Возьмем, в качестве примера, исходной пирамиду h1, ...,h7, показанную на рисунке 7.5, и расширим эту пирамиду влево, добавив к ней элемент h1 = 44.

Новый элемент, в нашем случае это - h1 = 44, сначала помещается в вершину дерева, а затем «просеивается» по пути, на котором находятся меньшие по сравнению с ним элементы, которые, в свою очередь, поднимутся вверх, так как их значение меньше помещаемого в дерево элемента. В нашем случае 44 меняется местами с 06, затем с 12, и так формируется дерево, показанное на рисунке 7.6.

06

122

44

42

94

55

18

Рис.7.6.Просеивание ключа - 44 через пирамиду.

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

Алгоритм быстрой сортировки (quicksort) был разработан К.А.Р. Хоаром (C.A.R. Hoare) в 1960 году. В настоящее время он является самым широко используемым в программировании методом сортировки, что вызвано его крайне положительными характеристиками: это алгоритм класса O(n×log(n)) для общего случая, он требует лишь незначительного объёма дополнительной памяти, работает с различными типами массивов и достаточно удобен для реализации. Также быстрая сортировка имеет несколько нежелательных характеристик: при его реализации допускается слишком много ошибок, быстродействие в худшем случае составляет O(n²) и к тому же она неустойчива.^[8]

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

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

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

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

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

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

После выбора базового элемента перейдём к описанию алгоритма разбиения массива. Будем оперировать с двумя индексами: первый будет использоваться для прохождения по элементам массива слева направо, второй - справа налево. Начинаем справа и идём к левому краю массива, сравнивая значение каждого элемента со значением базового элемента. Выполнение цикла завершается, если найден элемент, значение которого меньше или равно значению базового элемента. Это был внутренний цикл № 1: сравнение двух элементов и уменьшение значения индекса. Затем та же операция выполняется слева. Проход выполняется к правому концу массива. Значение каждого элемента сравнивается со значением базового элемента. Выполнение цикла завершается, если найден элемент, значение которого больше или равно значению базового элемента. Это был внутренний цикл № 2: сравнение двух элементов и увеличение значения индекса.^[9]

Заключение

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива a в массив b, не представляет для нас интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов мы проводим в соответствии с их эффективностью, т. е. экономией времени или быстродействием.

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

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

Рассмотрев усовершенствованные методы сортировки срав­ним их эффективность. Как и раньше, n — число сортируемых элементов, а С и М — соответственно число необходимых сравне­ний ключей и число обменов. Для всех прямых методов сорти­ровки можно дать точные аналитические формулы. Для усовершенствованных методов нет сколько-либо осмыслен­ных, простых и точных формул. Существенно, однако, что в слу­чае сортировки Шелла вычислительные затраты составляют с×n^1.2, а для пирамидальной сортировки и метода быстрой сортировки — с×n×logn, где с — соответствую­щие коэффициенты.

Эти формулы просто вводят грубую меру для производитель­ности как функции n и позволяют разбить методы сортиров­ки на примитивные, прямые методы (n²) и на усложненные или "логарифмические" методы (n×log(n)).

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

Итак, сделаем вывод: алгоритмы устойчивой сортировки - самые медленные алгоритмы сортировки, принадлежащие к классу О(n²), применяются при небольшом n. Алгоритмы неустойчивой сортировки – наиболее быстрые, принадлежащие к классу О(n×log(n)), применяются при большом n. Выбор определенного метода сортировки зависит от структуры обрабатываемых данных, а также от количества элементов. При решении определенной задачи, выбранный метод сортировки должен быть наиболее эффективным.

Список использованной литературы

1. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с.
2. Вирт Н. Книга: Алгоритмы и структуры данных. [Текст] / Н.Вирт. Перевод с английского – М. Издательство «Мир», 1989. -358 с.
3. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. [Текст] = Алгоритмы: построение и анализ, 2-издание. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Перевод с английского – М. Издательский дом «Вильямс», 2005. – 1296 с.
4. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с.

1. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

2. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

3. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

4. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

5. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

6. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

7. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

8. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

9. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑