Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ЛАБОРАТОРНАЯ РАБОТА №9.
Тема: Алгоритмы сортировок массивов данных.
Цель работы: Знакомство с основными алгоритмами сортировок массивов данных, классификация этих алгоритмов в соответствии с их эффективностью.
Используемые программные средства: Delphi.
1. Теоретические сведения:
1.1. Методы сортировки
Под сортировкой обычно понимают процесс целенаправленной перестановки элементов данных в определенном порядке по возрастанию или убыванию согласно определенным линейным отношениям их порядка, таким как отношения или для чисел. Цель сортировки – облегчить в дальнейшем поиск элемента в отсортированной (упорядоченной) совокупности элементов. Это напоминает поиск элемента в словаре, телефонном справочнике, ведомостях и так далее.
Методы сортировки очень нужны при обработке данных. С сортировкой связаны многие фундаментальные приемы построения алгоритмов. Сортировка является идеальным примером огромного разнообразия алгоритмов, которые исполняют одну и тую же задачу, многие из которых в некотором смысле являются оптимальными, а большинство имеет некоторые преимущества по сравнению с остальными. Поэтому на примере сортировки можно убедиться в необходимости сравнительного анализа алгоритмов. Здесь можно увидеть, как при помощи усложнения алгоритма можно получить существенное увеличение эффективности при сравнении с более простыми и очевидными алгоритмами.
Зависимость выбора алгоритма от структуры данных – явление довольно частое, и в случае сортировки это особо сильно ощущается, поэтому методы сортировки обычно разделяют на две категории:
Эти два класса часто называют внутренней и внешней сортировкой, поскольку массивы размещаются в оперативной памяти быстрого доступа к каждому элементу, а последовательные файлы сохраняются в более медленной, но более емкой памяти, когда доступ имеем только к текущему элементу.
Сортировка строк – это ранжирование данных строкового типа по алфавиту (фактически по номеру составляющих строку символов в ASCII-коде).
Отметим, что сортировка строк или элементов файла с прямым (а не последовательным) доступом во всем напоминает сортировку массивов, поскольку доступ имеем к каждому элементу.
Введем систему обозначений, которую будем использовать в дальнейшем. Пусть нам даны элементы , , …, .
Сортировка по возрастанию (убыванию) означает перестановку этих элементов в таком порядке: , , …, , что при заданной функции упорядочения справедливы отношения: (или наоборот ).
Обычно функция упорядочения не подсчитывается по какому-то специальному правилу, а присутствует в каждом элементе в виде явной компоненты (поля элемента), которую называют ключом элемента. Таким образом, для представления элемента особенно хорошо подходит структура записи. Для дальнейшего рассмотрения материала определим тип item, который будет использоваться в алгоритмах сортировки так:
Const n = ...;
Type inf = record
...
end ;
item = record
key : integer;
Zmest : inf; {описание «других компонентов»}
end;
Index = 0..n;
«Другие компоненты» – это все существенные данные об элементе. Поле key – ключ, и служит только для идентификации элемента. Но если мы говорим об алгоритмах сортировки, ключ для нас – единственная существенная компонента, и у нас нет необходимости определять остальные. Тип ключа может быть любым типом, для которого заданы отношения всеобщего порядка «больше или равно» («меньше или равно»).
Введём еще такое обозначение:
Var A: array [1..n] of item;
Метод сортировки будем называть устойчивым, если относительный порядок элементов с одинаковыми ключами не изменяется при сортировке. Устойчивость сортировки часто бывает желательна, если элементы упорядочены (отсортированы) по каким-то второстепенным ключам, т.е. по свойствам, которые не отражены в первоначальном ключе.
Разберем подробно некоторые интересные алгоритмы сортировки.
1.2. Сортировки массивов
Основное требование для методов сортировки массивов – экономное использование памяти. Это значит, что перераспределение элементов нужно выполнять на том же месте {in site}, и поэтому методы, которые пересылают элементы из массива А в массив В для нас не представляют интереса.
Таким образом, выбирая метод сортировки и руководствуясь критериями экономии памяти, классификацию алгоритмов мы будем проводить в соответствии с их эффективностью, это значит экономией времени и быстротой действия. При этом будем подсчитывать С – необходимое количество сравнений ключей и М – пересылок элементов (что отнимает много времени). Это будут функции от n – числа сортируемых элементов.
Методы, сортирующие элементы in site, можно разбить на три основных класса в зависимости от заложенного в их основе приема (базового алгоритма):
Рассмотрим методы сортировки массивов в соответствии с этой классификацией и сразу будем отыскивать те подходы, которые позволяют улучшать базовый алгоритм.
При различных методах сортировки интерес будут вызывать такие вопросы:
2. Сортировки обменом
2.1. Сортировка простым обменом (метод пузырька)
Идея: упорядоченный массив А получается из исходного массива А систематическим обменом пары рядом находящихся элементов, которые не соответствуют нужному порядку упорядочения, пока такие пары находятся при просмотре массива.
Просмотр массива будем осуществлять справа налево (можно и наоборот). Этот алгоритм называется сортировка «пузырьком», поскольку минимальный элемент как бы всплывает (как пузырек) в начало массива при просмотре этого массива.
Рассмотрим работу такого алгоритма на следующем примере (n=8):
44, 55, 12, 42, 94, 18, 06, 67
В следующей таблице в столбцах отражены промежуточные состояния сортируемого массива.
Таблица. Пример сортировки методом пузырька
|
Начальные ключи |
i=2 |
i=3 |
i=4 |
i=5 |
i=6 |
i=7 |
i=8 |
|
44 |
06 |
06 |
06 |
06 |
06 |
06 |
06 |
|
55 |
44 |
12 |
12 |
12 |
12 |
12 |
12 |
|
12 |
55 |
44 |
18 |
18 |
18 |
18 |
18 |
|
42 |
12 |
55 |
44 |
42 |
42 |
42 |
42 |
|
94 |
42 |
18 |
55 |
44 |
44 |
44 |
44 |
|
18 |
94 |
42 |
42 |
55 |
55 |
55 |
55 |
|
06 |
18 |
94 |
67 |
67 |
67 |
67 |
67 |
|
67 |
67 |
67 |
94 |
94 |
94 |
94 |
94 |
Посчитаем количество сравнений:
Количество пересылок (обменов):
; ; ;
Можно заметить, что массив был отсортирован на некотором промежуточном шаге, однако алгоритм построен так, что это явление в нем не анализируется.
2.2. Сортировка простым обменом с флагом
Идея: этот метод является оптимизацией предыдущего метода – нужно запомнить, проводился ли при данном просмотре какой-нибудь обмен, и если нет, то можно досрочно завершить работу.
2.3. Сортировка простым обменом с границей
Идея: нужно запомнить не только факт обмена, но и запомнить индекс последнего обмена, так как понятно, что все пары соседних элементов с индексами меньшими этого индекса уже размещены в нужном порядке. Поэтому просмотр можно заканчивать на этом индексе вместо того, чтобы двигаться до конца.
2.4. Шейкер-сортировка
Следующий пример: 94, 55, 10, 12, 08, 44, 06, 67 (n=8) демонстрирует такое свойство, что при просмотре слева направо легкий элемент с каждым разом сдвигается на один шаг, а тяжелый сразу попадает в конец.
1-й просмотр: 55, 10, 12, 08, 44, 06, 67, 94
2-й просмотр: 10, 12, 08, 44, 06, 55, 67, 94
3-й просмотр: 10, 08, 12, 06, 44, 55, 67, 94
Отсюда сразу виден следующий подход.
Идея: используем смену направлений просмотра (→,←), поскольку один плохо размещенный «пузырек», «тяжелый» в «легком» конце, будет опускаться на нужное место за один проход, а «легкий» пузырек в «тяжелом» конце будет опускаться каждый раз только на один шаг.
Пример:
а) 94, 06, 12, 18, 42, 44, 55, 67; просмотр → сортирует массив за 1 проход;
б) 12, 18, 42, 44, 55, 67, 94, 06; тут понадобилось бы 7 проходов.
Схема работы алгоритма:
{1-й проход «←»} i:=n..2; id – индекс последней перестановки, значит уже упорядочен;
{2-й проход «→»} left:=id; i:=left..n; id – индекс последней перестановки, – осталось упорядочить. И так далее.
2.5. Быстрая сортировка
Рассмотрим последовательность элементов, отсортированных в обратном порядке. Как их быстро отсортировать в нужном порядке? Правильно, нужно выполнить обмен равноудаленных от концов элементов. Это наводит на определенные мысли, и получается такой улучшенный алгоритм:
Идея: выбираем некоторый элемент x данных – опорный элемент. Двигаемся по совокупности элементов слева направо, пока не встретим элемент , а потом – справа налево, пока не найдем элемент . Если i<j, то обменяем и . Продолжаем просмотр далее от позиции i+1 до j-1. Выполняем такой поиск до тех пор, пока два просмотра не встретятся.
Пусть в следующем примере: 55, 12, 42, 94, 06, 18, 44, 67 опорный элемент равен 42. Получим такую последовательность перемещений:
Дальше просмотр слева направо заканчивается на элементе 94, а справа налево на элементе 6. Они не обмениваются. Получили две части последовательности:
Поделив массив опорным элементом на две части, нужно сделать то же самое с каждой из них, а затем с частями этих частей и т.д., пока каждая часть не будет содержать только один элемент.
3. Сортировки включениями
3.1. Сортировка простым включением
Идея: элементы условно разделяются на готовую последовательность и входящую последовательность . На каждом шаге, начиная с i=2,3,…, берут и вставляют его на подходящее место в готовую последовательность.
Готовая последовательность упорядочена в порядке роста. Элемент x нужно вставить в нее не нарушая порядок, например, «просеять». Заметим, что «просеивание» может закончиться при двух условиях:
Когда становится ясно, куда нужно вставить элемент x, нужно освободить для него место, перемещая элементы на шаг вправо. Отметим, что это перемещение можно выполнять сразу при сравнении.
3.2. Сортировка бинарными вставками
Идея: можно получить улучшение предыдущего алгоритма, если поиск места вставки элемента x проводить бинарными делениями.
3.3. Сортировка Шелла
Следующий алгоритм представляет собой сортировку включениями с уменьшающимся приращением.
Идея: Сначала отдельно группируются и сортируются все элементы, которые отстоят один от другого на 4 позиции. Это четвертная сортировка (выполняем, пока не упорядочим). Дальше – двоичная сортировка (сортируются элементы, которые отстоят на дистанции 2; выполняем до упорядочения). На последнем проходе – обычная сортировка (одинарная).
На первый взгляд добавились 2 лишних шага (четвертная и двоичная сортировки), однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены.
Пример: Над следующим массивом выполним четвертную сортировку:
Результатом будет такой массив:
Выполним двоичную сортировку и получим следующий массив:
Выполним одинарную сортировку и получим полностью отсортированный массив:
Заметим, что продвижение «легкого» элемента вперед идет довольно быстрыми темпами.
Очевидно, что этот метод дает в результате упорядоченный массив. Также ясно, что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-я сортировка объединяет две группы, отсортированные предыдущей сортировкой. Анализ показал, что приемлема произвольная последовательность приращений, с условием, что последнее приращение равно 1, так как в худшем случае вся работа будет выполнена при последнем проходе. Отметим также, что, как показывает практика, если приращение не является степенью двойки, то можно получить гораздо лучшие результаты сортировки.
4. Сортировки выбором
4.1. Сортировка простым выбором
Идея: среди n элементов выбирается элемент с наименьшим ключом, и меняется местами с первым. Затем действие повторяется с оставшимися n-1 элементами, n-2 элементами и так далее, пока не останется один последний элемент.
Пример:
i=1 44 55 12 42 94 18 06 67
i=2 06 55 12 42 94 18 44 67
i=3 06 12 55 42 94 18 44 67
i=4 06 12 18 42 94 55 44 67
i=5 06 12 18 42 94 55 44 67
i=6 06 12 18 42 44 55 94 67
i=7 06 12 18 42 44 55 94 67
i=8 06 12 18 42 44 55 67 94
4.2. Пирамидальная сортировка
Улучшить предложенный выше метод можно, если после каждого сравнения сохранять больше информации об элементах. Например, 1-й шаг: при помощи n/2 сравнений можно определить наименьший ключ из каждой пары; 2-й шаг: при помощи n/4 сравнений из выбранных ключей определить наименьший из каждой пары и так далее. Получим за меньшее количество сравнений наименьший из n элементов в корне дерева.
На втором этапе мы спускаемся по пути, указанному наименьшим ключом и исключаем его, заменяя, например, на ∞. Дальше по той же схеме находим наименьший среди оставшихся элементов. После n таких шагов дерево становится пустым (состоит из дырок), значит процесс сортировки закончился.
Каждый из n шагов требует сравнений (так как уменьшение шло каждый раз в два раза), тогда за n шагов получаем сравнений, в то время как первоначальный метод требует сравнений.
Однако реализация этого метода требует дополнительную память для хранения дерева – информации после каждого из сравнений. Поэтому нужно найти более удобный метод хранения дерева и каким-то образом освободиться от необходимости сохранять «дырки».
Оригинальный метод нашел Дж.Вильямс и назвал его пирамидальной сортировкой.
Пирамида определяется как последовательность ключей , такая, что выполняются условия:
, (*)
для всех .
Отсюда . Фактически получается следующее дерево:
Встают вопросы: как строить и хранить пирамиду. Оказалось, что это можно делать in site.
Допустим, что задана пирамида с элементами , (l и r – фиксированные). Нужно добавить новый элемент x так, чтобы сформировать расширенную на этот элемент пирамиду . Если новый элемент сначала добавить в вершину дерева, а затем «просеивать» по пути, на котором находятся меньшие в сравнении с ним элементы, которые одновременно поднимаются вверх, тогда сформируется новая (расширенная на один элемент) пирамида, так как при этом выполняется условие (*).
Рассмотрим пример. Пусть задана пирамида ; , , , , , .
Нужно добавить в нее новый элемент 44. Берем . По условию (*) сравнивается с меньшим из и . Это , и он обменивается с . Получится и . Дальше сравнивается с меньшим из и . Это , и он обменивается с . Получилась расширенная пирамида 6, 42, 12, 55, 94, 18, 44.
Основываясь на этом приеме просеивания, красивый способ построения пирамиды in site был предложен Р.У.Флойдом. Рассмотрим его.
Дан массив . Ясно, что элементы уже образовывают пирамиду, поскольку для тут не существует элементов с номерами 2i и 2i+1. (1-й этап). Начиная с элемента i=n/2 с шагом -1 до 1 будем просеивать через предыдущую пирамиду очередной элемент. В конце этой процедуры в вершину пирамиды вытолкнется самый маленький элемент. Но последовательность еще не отсортирована. Сделаем следующее. (2-й этап). Обменяем первый элемент с последним и просеем его через пирамиду, не трогая последнего. Новый первый элемент обменяем с предпоследним и просеем его через пирамиду, не трогая двух последних. И так сделаем n-1 раз. Получим упорядоченный массив по спаданию значений.
Отобразим первый этап на следующем примере.
44 55 12 42 | 94 18 06 67 ( сравнивается с и остается на месте)
44 55 12 | 42 94 18 06 67 ( сравнивается с меньшим из и , и обменивается с )
44 55 | 06 42 94 18 12 67
44 | 42 06 55 94 18 12 67
06 42 12 55 94 18 44 67
Этим мы сформировали пирамиду и наименьший элемент вытолкнули наверх. Дальше будем обменивать его согласно этапу 2.
67 42 12 55 94 18 44 | 06 → 12 42 67 55 94 18 44 | 06 →
12 42 18 55 94 67 44 | 06 → 44 42 18 55 94 67 | 12 06 →
18 42 44 55 94 67 | 12 06 → 18 42 44 55 94 67 | 12 06 →
67 42 44 55 94 | 18 12 06 → 42 55 44 67 94 | 18 12 06 →
94 55 44 67 | 42 18 12 06 → 44 55 94 67 | 42 18 12 06 →
67 55 94 | 44 42 18 12 06 → 55 67 94 | 44 42 18 12 06 →
94 67 | 55 44 32 18 12 06 → 67 94 | 55 44 42 18 12 06 →
94 | 67 55 44 32 18 12 06.
Получили упорядоченный массив по убыванию значений.
Значит, чтобы получить упорядочение в другую сторону, нужно изменить условие (*) на противоположное.
5. Сравнительный анализ сортировок
Мы получили следующие алгоритмы:
I. Сортировки обменом:
II. Сортировки включениями
III. Сортировки выбором
Попробуем провести сравнительный анализ их эффективности.
Пусть n – по прежнему обозначает число сортируемых элементов, а С и М – соответственно количество необходимых сравнений ключей и пересылок элементов. Для всех трех простых методов сортировки можно дать замкнутые аналитические формулы. Они приведены в следующей таблице (заголовки столбцов Min, Max, Средн. определяют максимумы, минимумы и ожидаемые средние значения для всех n! перестановок n элементов):
Таблица: Сравнение простых методов сортировки
|
Min |
Средн |
Max |
|
|
Простые включения |
C=n-1 M=2(n-1) |
(n2+n-2)/4 (n2-9n-10)/4 |
(n2-n)/2-1 (n2+3n-4)/2 |
|
Простой выбор |
C=(n2-n)/2 M=3(n-1) |
(n2-n)/2 n(lnn+0,57) |
(n2-n)/2 n2/4+3(n-1) |
|
Простой обмен (метод пузырька) |
C=(n2-n)/2 M=0 |
(n2-n)/2 (n2-n)*0,75 |
(n2 -n)/2 (n2-n)*1,5 |
Для усовершенствованных методов нет достаточно простых и точных формул (некоторые приблизительные оценки см. в приложении, таблица 4). Все, что можно сказать, это то, что стоимость вычислений равна в случае сортировки Шелла и в случаях пирамидальной и быстрой сортировок.
Эти формулы дают лишь приблизительную оценку эффективности как функции от n; они допускают классификацию алгоритмов сортировки на простые (n2) и усовершенствованные, или «логарифмические» (n∙logn). Однако для практических целей полезно иметь некоторые экспериментальные данные, которые могут пролить свет на коэффициенты , позволяющие проводить дальнейшую оценку различных методов.
Рассмотрим экспериментально полученные данные на примере массивов из 160, 2560 и 10240 элементов (см. приложение, таблицы 1-3). Массивы различной длины и различной начальной упорядоченности (по возрастанию, по убыванию, не упорядоченные) были отсортированы в порядке возрастания и убывания.
Анализируя полученные данные, нетрудно заметить, что сортировка методом пузырька (с улучшениями) определенно является наихудшей среди всех сравниваемых методов, и даже ее улучшенная версия – шейкер-сортировка – все-таки хуже, чем сортировка простыми включениями и простым выбором (кроме патологического случая сортировки уже рассортированного массива).
Очевидно также, что преимущество сортировки бинарными включениями по сравнению с сортировкой простыми включениями ничтожно, хотя оба этих метода заметно превосходят алгоритмы сортировки обменом.
Наиболее выгодными алгоритмами являются быстрая и пирамидальная сортировки, причем быстрая сортировка превосходит пирамидальную в отношении 2 к 3. Она сортирует массив с элементами, расположенными в обратном порядке практически так же, как уже рассортированный массив.
Результаты практически того же порядка показывает сортировка Шелла, особенно в случае уже рассортированного массива. Однако в случае неупорядоченного массива ее эффективность заметно снижается при увеличении количества элементов массива.
Следующие диаграммы иллюстрируют сравнительный анализ трех наиболее выгодных сортировок (быстрой, пирамидальной и Шелл- сортировок) применительно к неупорядоченным массивам различной длины при их сортировке в порядке увеличения ключей.
Таким образом, самым быстрым методом и действительно лучшим алгоритмом сортировки оказалась быстрая сортировка, а наихудшим – сортировка методом пузырька.
6. Контрольные вопросы
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3