Лабораторная работа 2.

Сортировка значений в таблице.

Цель работы: изучение методов сортировки массивов.

Исходные теоретические сведения

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= I

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

Классы алгоритмов сортировки

Имеется три способа сортировки массивов:

• сортировка обменом;

• сортировка выбором;

• сортировка вставкой.

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

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

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

Сортировка Шелла

Сортировка Шелла получила свое название по имени ее создателя Д.Л. Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга. ("Ракушка" - одно из значений слова shell).

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

• проход 1 f d a c b e

• проход 2 c b a f d e

• проход 3 a b c e d f

• полученный результат a b c d e f procedure shell(var a:massiv;p:word); const

t=5;

var

i,j,k,s,m:integer; h:array[1..t] of integer; x:data; begin

writeln('Сортировка Шелла:'); h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1; for m:=1 to t do begin

k:=h[m];

s:=-k;

for i:=k+1 to p do begin x:=a[i]; j:=i-k; if s=0 then begin s:=-k; s:=s+1; a[s]:=x; end;

while (x<a[j]) and (j<p) do begin

a[j+k]:=a[j];

^j:=^j-k;

end;

a[j+k]:=x;

end;

end;

end;

При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных. Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3,

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

Внутренний цикл имеет два условия проверки. Условие "х<а[П" необходимо для упорядочения элементов. Условия "j>0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "а". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки. Анализ сортировки Шелла требует решения некоторых сложных математических задач Время выполнения сортировки Шелла пропорционально nl.2. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки.

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

Пример выполнения.

Задание: составить алгоритм и программу сортировки массива методом Шелла.

Блок-схема алгоритма

	^ Начало ^
i	/озд. массива
1
	вывод массива
	сорт. Шелла

ечать

рез-та

V

j,k,p,t,m,x

j

Г>< ^m=^{1, t}

ITT

k=h[m];s=-k

с

Конец

x=a[i]

j=i-k

Текст программы: uses crt; type

data=integer;

massiv=array[1..15] of integer; var a,b:massiv; n,i:word;

procedure create_massive(var a:massiv;p:word); var i:word; begin

writelnCМассив создан:');

for i:=1 to p do

begin

a[i]:=2*(9+random(100));

write(a[i]:5);

end;

end;

procedure vivod_massive(var a:massiv;p:word); var i:word; begin

for i:=1 to p do write(a[i]:5); end;

procedure shell(var a:massiv;p:word); const t=5; var

i,j,k,s,m:integer; h:array[1..t] of integer;

x:data;

begin

writelnCСортировка Шелла:'); h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1; for m:=1 to t do begin k:=h[m]; s:=-k;

for i:=k+1 to p do begin

x:=a[i];

j:=i-k; if s=0 then begin s:=-k; s:=s+1; a[s]:=x; end;

while (x<a[j]) and (j<p) do begin

a[j+k]:=a[j];

^j:=^j-k;

end;

a[j+k]:=x;

end;

end;

end;

begin

clrscr;

write('Введите число элементов массива 2..15: '); readln(n);

create_massive(b,n);

writeln;

shell(b,n);

vivod_massive(b,n);

readkey;

end.

Результаты расчетов:

Р" Turbo Pascal
|Введнте число элементов	массива	2..15: 10
Массив создан:
18 24 190 58	72 152	80 50	92	102
Сортировка Шелла:
18 24 50 58	72 80	92 102	152	190

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

Вариант	Задание
1	Разработать алгоритм и программу внутренней сортировки значений в таблице(пузырьковая сортировка).
2	Разработать алгоритм и программу внутренней сортировки значений в таблице (сортировка простыми вставками).
3	Разработать алгоритм и программу внутренней сортировки значений в таблице (простая сортировка выбором).
4	Разработать алгоритм и программу внутренней сортировки значений в таблице (метод Шелла).
5	Разработать алгоритм и программу внутренней сортировки значений в таблице (бинарные вставки).
6	Разработать алгоритм и программу внутренней сортировки значений в

	таблице (быстрая сортировка).
7	Разработать алгоритм и программу внутренней сортировки значений в таблице (сортировка выбором).
8	Разработать алгоритм и программу внешней сортировки значений в таблице (простое слияние).
9	Разработать алгоритм и программу внешней сортировки значений в таблице (естественное слияние).
10	Разработать алгоритм и программу внешней сортировки значений в таблице (улучшенные методы сортировки).

Вывод: изучить методы сортировки массивов.