Сортировка методом вставок. Бинарные и двухпутевые вставки

64 Original pages: 118-120

Задание на курсовую работу

По дисциплине: «Технология разработки программных продуктов»

Тема: Сортировка методом вставок. Бинарные и двухпутевые вставки

Резюме

Цель работы: исследование алгоритмов сортировки методом бинарных и двухпутевых вставок

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

Достижение цели работы предполагает решение следующих задач:

проанализировать известный алгоритм быстрой сортировки массива;

разработать программу, реализующую рассматриваемый алгоритм;

сформулировать и реализовать численный пример работы алгоритма.

Введение

Сортировка -- одна из наиболее распространённых операций обработки данных. Сортировкой называется распределение элементов множества по группам в соответствии с определёнными правилами. Например, в одномерном массиве X из N элементов требуется произвести перестановку значений так, чтобы они расположились по возрастанию, т.е. X1 ? X2 ? XN .

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

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

Время -- основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение -- это и плохое поведение -- это . Идеальное поведение для упорядочения -- . Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью , использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за операций. При этом число n должно быть заранее известно;

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

Глава 1. Сортировка вставками

Сортировка вставками -- простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

прост в реализации;

эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

эффективен на наборах данных, которые уже частично отсортированы;

это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

может сортировать список по мере его получения;

не требует временной памяти, даже под стек.

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

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

1.1 Простые вставки

Простейшая сортировка вставками относится к наиболее очевидным.

Пусть 1 < j ? N и записи R1, ..., Rj-1 уже размещены так, что K1 ? K2 ?...? Kj-1.

Будем сравнивать по очереди Kj с Kj-1, Kj-2, ..., Kj-1 до тех пор, пока не обнаружим, что запись Rj следует вставить между Ri, и Ri+1; тогда подвинем записи Ri+1,... Rj-1 на одно место вверх и поместим новую запись в позицию i+1. Удобно совмещать операции сравнения и перемещения, перемежая их друг с другом, как показано в следующем алгоритме; поскольку запись R, как бы "проникает на положенный ей уровень", этот способ часто называют просеиванием, или погружением.

Алгоритм S. (Сортировка простыми вставками.) Записи R1, ..., RN переразмещаются на том же месте; после завершения сортировки их ключи будут упорядочены: K1 ? ...? KN

S1. [Цикл по j.] Выполнить шаги от S2 до S5 при j = 2,3, ..., N и после этого завершить алгоритм.

S2. [Установить i, К, R] Установить i < j-1, К < Кj, R < Rj (В последующих шагах мы попытаемся вставить запись R в нужное место, сравнивая K с Кi, при убывающих значениях i.)

S3. [Сравнить K с Кi] Если K ? Ki, то перейти к шагу S5. (Мы нашли искомое место для записи R.)

S4. [Переместить Ri, уменьшить i.] Установить Ri+1 < Ri, i < i - 1. Если i > 0, то вернуться к шагу S3. (Если i = 0, то К . наименьший из рассмотренных до сих пор ключей, а, значит, запись R должна занять первую позицию.)

S5. [R на место Ri+1] Установить Ri+1 < R.

В Табл. 1 показано применение алгоритма S к шестнадцати числам; взятым нами для примеров.

S1. Цикл по j

S2. Установить i, К, R

S4. Переместить Ri, уменьшить i

S3.Сравнить K, Kij > N

2 ? j? N

i = 0

i > 0

S5. R на место Ri+1< ?

Таблица 1

Пример применения простых вставок

Исходные данные:

503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

Процесс сортировки:

503:087

087 503:512

087 503 512:061

061 087 503 512:908

061 087 5033 512 908:170

061 087 170 503 512 908:897

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

061 087 154 170 275 426 503 509 512 612 653 677 765 897 908:703

061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

Время работы этого алгоритма равно 9B + 10N - 3А - 9 единиц, где N . число сортируемых записей, А - число случаев, когда в шаге S4 значение i убывает до 0, а В . число перемещений.

Приведенные в качестве примера в Табл. 1 данные содержат 16 элементов; имеются два левосторонних минимума, 087 и 061, и 41 инверсия. Следовательно, N=16, A=2, B=41, а общее время сортировки равно 514 ед.

1.2 Бинарные вставки

Когда при сортировке простыми вставками обрабатывается j-я запись, ее ключ сравнивается в среднем примерно с j/2 ранее отсортированными ключами; поэтому общее число сравнений равно приблизительно (1 +2+ ... +N) /2 ? 4 N2 , а это очень много, даже если N умеренно велико. Методы "бинарного поиска" указывают, куда вставлять j-й элемент после приблизительно j 2 log соответствующим образом выбранных сравнений.

Например, если вставляется 64-я запись, можно сначала сравнить ключ K64 с K32; затем, если он меньше, сравниваем его с K16, если больше.с K48 и т. д., так что место для R64 будет найдено после всего лишь шести сравнений. Общее число сравнений для N вставляемых элементов равно приблизительно N N 2 log , что существенно лучше, чем 4

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

Неприятность состоит в том, что бинарные вставки решают задачу только наполовину: после того, как мы нашли, куда вставлять запись Rj, все равно нужно подвинуть примерно j/2 ранее отсортированных записей, чтобы освободить место для Rj, так что общее время работы остается, по существу, пропорциональным N2. Некоторые вычислительные машины (например, IBM 705) имеют встроенные инструкции "переброски", выполняющие операции перемещения с большой скоростью, но с ростом N зависимость от N2 в конце концов начинает преобладать. Например, анализ, проведенный X. Нэглером [САСМ, 3 (1960), 618. 620], показывает, что не следует рекомендовать бинарные вставки при сортировке более N=128 записей на машине IBM 705, если каждая запись состоит из 80 литер; аналогичный анализ применим и к другим машинам.

Разумеется, изобретательный программист может придумать какие-нибудь способы, позволяющие сократить число необходимых перемещений; первый такой прием, предложенный в начале 50-х годов, проиллюстрирован в Табл. 2. Здесь первый элемент помещается в середину области вывода, и место для последующих элементов освобождается при помощи сдвигов влево или вправо, туда, куда удобнее.

1.3 Двухпутевые вставки

Таблица. 2

503

087 503

087 503 512

061 087 503 512

061 087 503 512 908

061 087 170 503 512 908

061 087 170 503 512 897 908

061 087 170 276 503 512 897 908

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

Метод Шелла. Для алгоритма сортировки, который каждый раз перемещает запись только на одну позицию, среднее время работы будет в лучшем случае пропорционально N2, потому что в процессе сортировки каждая запись должна пройти в среднем через N/3 позиций (почему?). Поэтому, если мы хотим получить метод, существенно превосходящий по скорости простые вставки, то необходим некоторый механизм, с помощью которого записи могли бы перемещаться большими скачками, а не короткими шажками.

Такой метод предложен в 1959 г. Дональдом Л. Шеллом [САСМ, 2 (July, 1959), 30.32]; он также называется сортировкой с убывающим шагом. В Табл. 3 проиллюстрирована общая идея, лежащая в основе этого метода. Сначала делим 16 записей на 8 групп по две записи в каждой группе: (R1, R9), (R2, R10), ..., (R8, R16). В результате сортировки каждой группы записей по отдельности приходим ко второй строке Табл. 3, это называется "первым просмотром".

Сортировка с убывающим шагом (8, 4, 2, 1)

503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

8-сортировка:

503 087 154 061 612 170 765 275 653 426 512 509 908 677 897 703

4-сортировка:

503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703

2-сортировка:

154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703

1-сортировка:

061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

Заметим, что элементы 154 и 512 поменялись местами, а 908 и 897 переместились вправо.

Разделим теперь записи на четыре группы по четыре в каждой: (R1, R5, R9, R13), ...,(R4, R8, R12, R16) . и опять отсортируем каждую группу в отдельности; этот второй просмотр приводит к третьей строке таблицы. При третьем просмотре сортируются две группы по восемь записей; процесс завершается четвертым просмотром, во время которого сортируются все 16 записей. В каждом из этих промежуточных процессов сортировки участвуют либо сравнительно короткие файлы, либо уже сравнительно хорошо упорядоченные файлы, поэтому на каждом этапе можно пользоваться простыми вставками; записи довольно быстро достигают своего конечного положения.

Последовательность шагов 8, 4, 2, 1 не следует считать незыблемой, можно пользоваться любой последовательностью ht, ht-1, ..., h1, в которой последний шаг h1 равен 1. Некоторые последовательности оказываются гораздо лучше других.

Алгоритм D. (Сортировка с убывающим шагом) Записи R1, ..., RN переразмещаются на том же месте. После завершения сортировки их ключи будут упорядочены: K1 ? ...? KN. Для управления процессом сортировки используется вспомогательная последовательность шагов ht, ht-1, ..., h1, где h1 = 1; правильно выбрав эти приращения, можно значительно сократить время сортировки. При t = 1 этот алгоритм сводится к алгоритму S.

D1. [Цикл по s.] Выполнить шаг D2 при s = t, t.1, ..., 1, после чего завершить работу алгоритма.

D2. [Цикл по j.] Установить h < hs, и выполнить шаги D3, ..., D6 при h < j ? N.

D3. [Установить i, К, R] Установить i < j - h, К < Кj, R < Rj

D4. [Сравнить К, Кi] Если К, ? Кi, то перейти к шагу D6.

D5. [Переместить Ri, уменьшить i.] Установить Ri+h < Ri, i < i - h. Если i > 0, то вернуться к шагу D4.

D6. [R на место Ri+h] Установить Ri+h < R.

Глава 2. Практическая реализация алгоритмов

2.1 Сортировка методом бинарных вставок

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

uses crt;

type

mas=array[1..50] of integer;{линейный массив-строка матрицы}

matr=array[1..50] of mas;{массив строк-матрица}

procedure Sort_Str(var ms:mas;n:integer);{сортировка в строке}

var i,x,L,R,m,j:integer;

begin

for i:=2 to n do

begin

x:=ms[i];

L:=1; R:=i;

while L<R do

begin

m:=(L+R) div 2;

if ms[m]<=x then L:=m+1

else R := m;

end;

for j:=i downto R+1 do ms[j]:=ms[j-1];

ms[R]:=x;

end;

end;

procedure Sort_Matr(var mt:matr;n,k:integer);{сортировка строк, как элементов массива}

var i,x,L,R,m,j:integer;

st:mas;

begin

for i:=2 to n do

begin

x:=mt[i][k+1];{элемент в дополнительном столбце матрицы-произведение четных}

st:=mt[i];{строка матрицы}

L:=1; R:=i;

while L<R do

begin

m:=(L+R) div 2;

if mt[m][k+1]<=x then L:=m+1

else R:= m;

end;

for j:=i downto R+1 do

begin

mt[j][k+1]:=mt[j-1][k+1];{перемещаем элементы в доп. столбце}

mt[j]:=mt[j-1];{то же строки матрицы}

end;

mt[R][k+1]:=x;{вставляем элемент доп. столбца на место}

mt[R]:=st;{то же строки матрицы}

end;

end;

var n,m,i,j:integer;

p:longint;

a:matr;

begin

clrscr;

randomize;

write('Количество строк n=');readln(n);

write('Количество столбцов m=');readln(m);

writeln('Исходная матрица:');

for i:=1 to n do

begin

for j:=1 to m do

begin

a[i,j]:=random(9)+1;

write(a[i,j]:3);

end;

writeln;

end;

{сортировка в строках}

for i:=1 to n do

Sort_Str(a[i],m);

writeln('Результат сортировки в строках:');

for i:=1 to n do

begin

for j:=1 to m do

write(a[i,j]:3);

writeln;

end;

{вычисление произведений в строках и запись их в дополнительный массив}

for i:=1 to n do

begin

p:=1;

for j:=1 to m do

if a[i,j] mod 2=0 then p:=p*a[i,j];

a[i,m+1]:=p;

end;

{сортировка(перестановка строк)}

Sort_Matr(a,n,m);

writeln('Результат сортировки строк(последний столбец-произведение четных):');

for i:=1 to n do

begin

for j:=1 to m+1 do

if j=m+1 then{если элемент в последнем столбце}

if a[i,j]>1 then write(a[i,j]:6){и не 1, то выводим его с 6 знаками под число}

else write('Четных нет!':15){если 1, то сообщаем}

else write(a[i,j]:3);{остальные элементы по 3 позиции под число}

writeln;

end;

readln

end.

2.2 Сортировка методом двухпутевых вставок

procedure insert(var a: mas);

var

t, i, j, left, right: integer;

x: array[1..2 * n] of integer;

begin

left := n;

right := n;

x[n] := a[1];

for i := 2 to n do begin

t := a[i];

if t >= a[1] then begin

Inc(right);

j := right;

while t < x[j - 1] do begin

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

Dec(j);

end;

x[j] := t;

end

else begin

Dec(left);

j := left;

while t > x[j + 1] do begin

x[j] := x[j + 1];

Inc(j);

end;

x[j] := t;

end;

end;

for j := 1 to n do

a[j] := x[j + left - 1];

end;

Заключение

В данной курсовой работе были решены следующие задачи:

1. Проанализированы известные алгоритмы сортировки массива методами бинарных и двухпутевых вставок.

2. Разработана программа, реализующая рассматриваемый алгоритм;

3. Сформулирован и реализован численный пример работы алгоритма.

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

1. Алгоритмы и структуры данных/...Вирт: Пер. с англ. -2-е изд. , испр.--сПб:. Невский Диалект, 2001.--352 с.: ил.

2. Искусство программирования/...Кнут, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ.--М.: Издательский дом «Вильямс», 2001.--832 с.: ил.--Парал. тит. англ.

3. Материалы сайта forum.algolist.ru

4. Материалы сайта cyberforum.ru

5. Материалы сайта ru.wikipedia.org