Лабораторная работа в„–3ВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВВ Сортировка прямым обменом

 

1. Цель и задачи работы

Изучение метода сортировки массивов прямым обменом. Написание программы, демонстрирующей изученные принципы.

 

2. Теоретические сведения

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

В общем, сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки — облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Отсортированные объекты можно встретить на каждом шагу: в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где надо искать хранимые объекты. Даже малышей учат держать вещи «в порядке», и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики. Между сортировкой и арифметикой нет никакой видимой связи, да, по-видимому, и невидимой нет. Сортировка — некий «первичный» процесс человеческой деятельности.

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

Вот некоторые из наиболее важных применений сорти­ровки:

1. Решение задачи «группировки», РєРѕРіРґР° нужно собрать вместе РІСЃРµ элементы СЃ одинаковым значением некоторого признака. Допустим, имеется 10000 элементов, расположенных РІ случай­ном РїРѕСЂСЏРґРєРµ, причем значения РјРЅРѕРіРёС… РёР· РЅРёС… равны; Рё предпо­ложим, нам нужно переупорядочить файл так, чтобы элементы СЃ равными значениями занимали соседние позиции РІ файле. Это, РїРѕ существу, задача «сортировки» РІ широком смысле слова, Рё РѕРЅР° легко может быть решена путем сортировки файла РІ. СѓР·РєРѕРј смысле слова, Р° именно расположением элементов РІ неубываю­щем РїРѕСЂСЏРґРєРµ v₁ ВЈ v₂ ВЈ … ВЈ v₁₀₀₀₀ .

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

Теперь четко опре­делим задачу и введем соответствующую терминологию. Пусть надо упорядочить N элементов

R₁, R₂, …, R_N.

Назовем их записями, а всю совокупность N записей назовем файлом. Каждая запись R_j имеет ключ К_j, который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную «сопутствующую информацию», которая не влияет на сортировку, но всегда остается в этой записи.

Отношение порядка «<» на множестве ключей вводится таким образом, чтобы для любых трех значений ключей а, b, c выпол­нялись следующие условия:

1) справедливо одно и только одно из соотношений: а<b, a=b, b<a (закон трихотомии);

2) если а<b и b<с, то а<с (закон транзитивности).

Эти два свойства определяют математическое понятие линейного упорядочения, называемого еще совершенным упорядочением. Любое множество с отношением«<», удовлетворяющим вышеперечисленным свой­ствам, поддается сортировке большинством методов.

Задача сортировки — найти такую перестановку записей p(1), p(2),...,p(N), после которой ключи расположились бы в не­убывающем порядке:

K_p(1), K_p(2), …, K_p(N).

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

p(i)<p(j), если K_p(i)=K_p(j) и i<j.

Достаточно хороший общий алгоритм затрачивает РЅР° сорти­ровку N записей время РїРѕСЂСЏРґРєР° Nlog(N); РїСЂРё этом требуется около log(N)В«проходов» РїРѕ данным. Это минимальное время. Так, если удвоить число записей, то Рё время РїСЂРё прочих равных условиях возрастет немногим более чем РІРґРІРѕРµ.

 

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

 

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

Хорошей мерой эффективности может быть В— число необходимых сравнений ключей Рё — число пересылок (перестановок) элементов. Эти числа суть функции РѕС‚ числа сортируемых элементов. Как говорилось выше, если сортируется N элементов, то хорошим считается такой алгоритм сортировки, который требует РїРѕСЂСЏРґРєР° Nlog(N) сравнений. Для начала стоит рассмотреть самые простые алгоритмы, которые называют прямыми, требующими РїРѕСЂСЏРґРєР° N² сравнений. Прямые методы особенно СѓРґРѕР±РЅС‹ для объяснения характерных черт основных принципов большинства сортировок, программы этих методов легко понимать, Рё РѕРЅРё коротки. Усложненные же методы требуют небольшого чис­ла операций, РЅРѕ эти операции обычно сами более сложны, Рё поэтому для достаточно малых N прямые методы оказываются быстрее, хотя РїСЂРё больших N РёС… использовать, конечно, РЅРµ следует.

Методы сортировки «на том же месте» можно разбить в соответствии с определяющими их принципами на три основные категории:

1. Сортировки с помощью включения (by insertion)

2. Сортировки с помощью выделения (by selection)

3. Сортировка с помощью обменов (by exchange)

 

Сортировка с помощью прямого обмена

 

Пожалуй, наиболее очевидный СЃРїРѕСЃРѕР± обмен­ной сортировки это сравнивать K₁ СЃ Рљ₂, меняя местами R₁ Рё R₂, если РёС… ключи РЅРµ упорядочены, затем проделать то же самое СЃ R₂ Рё R₃, R₃ Рё R₄ Рё С‚.Рґ. РџСЂРё выполнении этой после­довательности операций записи СЃ большими ключами Р±СѓРґСѓС‚ про­двигаться вправо, Рё РЅР° самом деле запись СЃ наибольшим ключом займет положение R_N. РџСЂРё многократном выполнении этого процесса соответствующие записи попадут РІ позиции R_N-1, R_N-2 Рё С‚.Рґ., так что РІ конце концов, РІСЃРµ записи Р±СѓРґСѓС‚ упоря­дочены.

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

Можно предложить несколько путей улучшения метода пузырька. Заметим, что Р·Р° РѕРґРёРЅ просмотр элемент РЅРµ может переместиться более чем РЅР° РѕРґРЅСѓ позицию влево, так что если наименьший элемент вначале находится РІ правом конце, то нужно выполнить максимальное число сравнений. Это наводит РЅР° мысль Рѕ «шейкерной» сортировке (ShakerSort), РєРѕРіРґР° просмотр осуществляется попеременно РІ РѕР±РѕРёС… направлениях. РџСЂРё таком РїРѕРґС…РѕРґРµ среднее число срав­нений несколько сокращается. Это РїСЂРѕРёСЃС…РѕРґРёС‚ потому, что если R_j Рё R_j+1 РЅРµ меняются местами РїСЂРё РґРІСѓС… последовательных просмотрах РІ противоположных направлениях, то записи R_j Рё R_j+1 должны занимать СЃРІРѕРё окончательные позиции, Рё РѕРЅРё РјРѕРіСѓС‚ РЅРµ участ­вовать РІ последующих сравнениях. Например, просматривая перестановку 4 3 2 1 8 6 9 7 5 слева направо, получаем 3 2 1 4 6 8 7 5 9: записи R₄ Рё R₅ РЅРµ поменялись местами. РџСЂРё просмотре последней перестановки справа налево R₄ РІСЃРµ еще меньше (РЅРѕРІРѕР№) записи R₅; следовательно, можно сразу же сделать вывод Рѕ том, что записи R₄ Рё R₅ РјРѕРіСѓС‚ Рё РЅРµ участвовать РЅРё РІ РѕРґРЅРѕРј РёР· последующих сравнений.

 

 

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

 

Число сравнений в строго обменном алгоритме , а минимальное, среднее и максимальное число перемещений элементов (присваиваний) равно соответственно , , . Анализ же улучшенных методов, особенно шейкерной сортировки, довольно сложен. Минимальное число сравнений . Кнут считает, что для улучшенной пузырьковой сортировки среднее число проходов пропорционально , а среднее число проходов пропорционально . Следует обратить внимание на то, что все перечисленные выше усовершенствования не влияют на число перемещений, они лишь сокращают число излишних двойных проверок. Обмен местами двух элементов — чаще всего более дорогостоящая операция, чем сравнение ключей. «Обменная» сортировка и ее небольшие усовершенствования представляют собой нечто среднее между сортировками с помощью включения и с помощью выбора. Фактически в пузырьковой сортировке нет ничего привлекательного, кроме названия. Шейкерная сортировка используется в случаях, когда известно, что элементы почти упорядочены — на практике это бывает весьма редко.

 

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

 

Как можно оценить относительные преимущества РѕРґРЅРѕРіРѕ метода сортировки над РґСЂСѓРіРёРјРё РїСЂРё наличии РёС… значительного разнообразия? Разумеется, скорость исполнения сортировки важна, РЅРѕ РјРЅРѕРіРёРµ методы сортировки обладают уникальными характеристиками, влияющими РЅР° РёС… применимость РІ том или РёРЅРѕРј случае. Таким образом, РёРЅРѕРіРґР° среднюю скорость выполнения сортировки приходится сопоставлять СЃ РґСЂСѓРіРёРјРё факторами. Можно назвать четыре критерия, которые следует использовать РїСЂРё выборе метода сортировки: средняя скорость сортировки, скорость РІ наилучшем Рё наихудшем случаях, естественно ли его поведение, сортировка элементов СЃ совпадающими ключами.

Приведем оценку эффективности различных методов сортировки в соответствии с данными Н. Вирта (таблица 1). Как и раньше, N — число сортируемых элементов, а C и M соответственно число необходимых сравнений ключей и число обменов. Для всех прямых методов сортировки можно дать точные аналитические формулы. Столбцы Min, Avg, Max определяют соответственно минимальное, усредненное и максимальное по всем N! перестановкам из N элементов значения.

 

Таблица 1. Сравнение прямых методов сортировки

Метод
РџСЂСЏРјРѕРµ ВВВВВВВВвключение
РџСЂСЏРјРѕР№ ВВВВВВВВвыбор
РџСЂСЏРјРѕР№ВВ ВВВВВВВобмен

 

Приведем также время работы различных модификаций прямых методов сортировки.

В таблице 2 собраны времена работы различных вариаций методов сортировки в секундах, реализованных в системе Модула-2 на ЭВМ Lilith. Три столбца содержат времена сортировки уже упорядоченного массива, случайной перестановки и массива, расположенного в обратном порядке. В начале приводятся цифры для 256 элементов, а потом — для 2048. Кроме того, заслуживают внимания следующие особенности:

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

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

3. Quicksort лучше в 2-3 раза, чем Heapsort. Она сортирует массив, расположенный в обратном порядке, практически с той же скоростью, что и уже упорядоченный.

 

Таблица 2. Время работы различных программ сортировки

Метод	Разновидность	Упорядоченный	Случайный	Р’ обратномВВВ РїРѕСЂСЏРґРєРµ
n=256
РџСЂСЏРјРѕРµВВВ включение	StraightInsertion	0.02	0.82	1.64
BinaryInsertion	0.12	0.70	1.30
Прямой выбор	StraightSelection	0.94	0.96	1.18
РџСЂСЏРјРѕР№ВВВВВВВ обмен	BubbleSort	1.26	2.04	2.80
ShakerSort	0.02	1.66	2.92
Улучшенный пр. включения	ShellSort	0.10	0.24	0.28
Улучшенный пр. выбора	HeapSort	0.20	0.20	0.20
Улучшенные пр. обмена	QuickSort	0.08	0.12	0.08
NonRecQuickSort	0.08	0.12	0.08
	StraightMerge	0.18	0.18	0.18
n=2048
РџСЂСЏРјРѕРµВВВ включение	StraightInsertion	0.22	50.74	103.80
BinaryInsertion	1.16	37.66	76.06
Прямой выбор	StraightSelection	58.18	58.34	73.46
РџСЂСЏРјРѕР№ВВВВВВВ обмен	BubbleSort	80.18	128.84	178.66
ShakerSort	0.16	104.44	187.36
Улучшенный пр. включения	ShellSort	0.80	7.08	12.34
Улучшенный пр. выбора	HeapSort	2.32	2.22	2.12
Улучшенные пр. обмена	QuickSort	0.72	1.22	0.76
NonRecQuickSort	0.72	1.32	0.80

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

 

3. Схемы алгоритмов пузырьковой и шейкерной сортировок

 

На рисунке 1 представлена схема алгоритма пузырьковой сортировки, а на рисунке 2 — шейкерной сортировки.

 

РРёСЃ. 1. Схема алгоритма пузырьковой сортировки.

 

 

 

РРёСЃ. 2. Схема алгоритма шейкерной

Всортировки.

 

 

4. Пример программы на языке Pascal

Данная программа демонстрирует метод пузырьковой сортировки массива.

 

program lab5;

 

{$APPTYPE CONSOLE}

 

uses

В SysUtils;

 

const n = 20;

var a:array [0..n] of real;

var i,j:integer; x:real;

 

begin

Write('Упорядочивание последовательности, состоящей из 20');

Writeln('случайных чисел, с помощью пузырьковой сортировки');

Writeln('Несортированная последовательность:');

randomize;

for i:=0 to n-1 do

begin

ВВ a[i]:=random(100);

ВВ write(a[i],' ');

end;

 

for i:=1 to n-1 do

begin

ВВ for j:=n-1 downto i do

ВВ begin

ВВВВВ if a[j-1]>a[j] then

ВВВВВ begin

ВВВВВВВВ x:=a[j-1];

ВВВВВВВВ a[j-1]:=a[j];

ВВВВВВВВ a[j]:=x;

ВВВВВ end;

ВВ end;

end;

 

Writeln('Отсортированная последовательность:');

for i:=0 to n-1 do

begin

ВВ Write (a[i], ' ');

end;

readln;

end.

 

5. Варианты заданий

 

1. Реализовать метод пузырьковой сортировки Рё определить число необходимых перестановок Рё сравнений для уже упорядоченного массива, случайной перестановки Рё массива, расположенного РІ обратном РїРѕСЂСЏРґРєРµ.

2. Реализовать метод шейкерной сортировки элементов Рё определить число необходимых перестановок Рё сравнений для уже упорядоченного массива, случайной перестановки Рё массива, расположенного РІ обратном РїРѕСЂСЏРґРєРµ.

3. Реализовать РґРІР° прямых метода сортировки СЃ помощью обмена (пузырьковая Рё шейкерная) Рё сравнить число необходимых перестановок для уже упорядоченного массива, случайной перестановки Рё массива, расположенного РІ обратном РїРѕСЂСЏРґРєРµ.

4. Упорядочить массив методом РїСЂСЏРјРѕР№ обменной сортировки, состоящий РёР· n² элементов (РіРґРµ n=1, 2, 3, ...) Рё вывести его РІ РІРёРґРµ спирали (матрицы n РЅР° n).

ВВВВ Пример:

исходный массив для n=3:

1В 9В 8В 2В 3В 7В 6В 4В 5ВВ

после упорядочивания:

1В 2В 3В 4В 5В 6В 7В 8В 9

вывод:

1В 2В 3

8В 9В 4

7В 6В 5

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

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

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

8. Даны два массива A и B, каждый из которых состоит из n элементов (n=1, 2, 3, ...). Построить третий массив C, таким образом, что c_i=a_i+b_i (i=1,…,n). Отсортировать его по возрастанию, используя метод прямой обменной сортировки.

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

10. Даны два массива A и B, каждый состоит из n элементов (n=1,2,3, ...). Построить третий массив C, при условии, что c_i=a_i×b_i (i=1,...,n). Отсортировать его по убыванию, используя метод прямой обменной сортировки.

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

12. ВДаны РґРІР° массива A Рё B, каждый состоит РёР· n элементов (n=1,2,3,...). Построить третий массив C, РїСЂРё условии c_i=a_i–b_i (i=1,...,n). Отсортировать его РїРѕ возрастанию, используя метод РїСЂСЏРјРѕР№ обменной сортировки.

13. Реализовать метод пузырьковой сортировки Рё определить число необходимых перестановок Рё сравнений для уже упорядоченного массива, случайной перестановки Рё массива, расположенного РІ обратном РїРѕСЂСЏРґРєРµ.

14. Реализовать метод шейкерной сортировки элементов Рё определить число необходимых перестановок Рё сравнений для уже упорядоченного массива, случайной перестановки Рё массива, расположенного РІ обратном РїРѕСЂСЏРґРєРµ.

15. Реализовать РґРІР° прямых метода сортировки СЃ помощью обмена (пузырьковая Рё шейкерная) Рё сравнить число необходимых перестановок для уже упорядоченного массива, случайной перестановки Рё массива, расположенного РІ обратном РїРѕСЂСЏРґРєРµ.

16. Реализовать метод РїСЂСЏРјРѕР№ обменной сортировки Рё упорядочить РїРѕ убыванию массив, содержащий СЃСѓРјРјС‹ оценок студентов РіСЂСѓРїРїС‹. РќР° экран вывести СЃРїРёСЃРѕРє студентов Рё РёС… средний балл, СЃРїРёСЃРѕРє студентов, РёС… оценки, СЃСѓРјРјСѓ.

 

 

6. Указания по составлению отчета

 

Отчет должен содержать:

- название, цель лабораторной работы,

- постановку и описание задачи,

- решение задачи (схемы алгоритмов программ подпрограмм),

- текст составленной программы,

- тестовый пример,

- инструкцию пользователю,

- инструкцию программисту,

- краткие выводы.

 

 

Библиографический список

1. Вирт Н. Алгоритмы + структуры = программы: пер. с англ. М.: Мир, 1985.

2. Вирт Н. Алгоритмы и структуры данных: пер. с англ. М.: Мир, 1989.

3. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. Т.3. М.: Мир, 1977.