Реализация алгоритмов обменных сортировок при написании программы на Паскале

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

Краткие теоретические сведения

Существует три группы методов внутренней сортировки (сортировка включением, сортировка выбором, обменная сортировка). В данной лабораторной работе рассмотрены методы обменных сортировок.

Сортировка прямого обмена (пузырьковая)

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

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

Здесь и далее, во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива ( n ), на выходе - упорядоченный массив элементов(а).

Procedure Bubble_Sort(n:word;Var a:t);

Var

i,j:word;

x:integer;

Begin

For i:=2 To n Do

begin

For j:=n DownTo i Do

If a[j-1]>a[j] Then

begin

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

end

end

End;{Bubble_Sort}

Шейкерная сортировка

Улучшение алгоритма - это запоминать, производится ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот процесс улучшения можно продолжить, если запомнить не только сам факт обмена, но и место (индекс) последнего обмена. Все пары соседних элементов с индексами, меньшими этого индекса k, уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе, вместо того чтобы двигаться до установленной заранее нижней границы i.

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

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

Procedure Shaker_Sort(n:word;Var a:t);

Var

j,k,l,r:word;

x:integer;

Begin

l:=2; r:=n; k:=n;

Repeat

For j:=r DownTo l Do

If a[j-1]>a[j] Then

begin

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

end;

l:=k+1;

For j:=l To r Do

If a[j-1]>a[j] Then

begin

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

end;

r:=k-1;

Until l>r

End;{Shaker_Sort}

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

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

Предположим, что дана пирамида с элементами h_l+1,..., h_r для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду h_l,..., h_r. Новый элемент x сначала помещается в вершину дерева, а затем “просеивается” по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом, формируется новая пирамида.

Здесь в процедуре Heap_Sort вызывается процедура Sift, которая реализует алгоритм формирования пирамиды.

Procedure Heap_Sort(n:word;Var a:t);

Var

l,r:word;x:integer;

Procedure Sift;

Label 13;

Var i,j:word;

Begin

i:=l; j:=2*i; x:=a[i];

While j<=r Do

begin

If j<r Then

If a[j]<a[j+1] Then j:=j+1;

If x>=a[j] Then Goto 13;

a[i]:=a[j]; i:=j; j:=2*i;

end;

13: a[i]:=x

End;{Sift}

BEGIN

l:=(n div 2)+1; r:=n;

While l>1 Do

begin

l:=l-1; Sift

end;

While r>1 Do

begin

x:=a[1]; a[1]:=a[r]; a[r]:=x;

r:=r-1; Sift

end

END;{Heap_Sort}

Обменная сортировка разделением

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

Выбирается любой произвольный элемент массива, далее массив просматривается слева направо до тех пор пока не будет найден элемент больший выбранного; а затем просмотрим его справа налево, пока не найдем элемент меньший выбранного. Найденные элементы поменяем местами. Затем продолжим процесс “просмотра с обменом”, пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими выбранного элемента; и правую - с большими ключами. Описанный алгоритм применяется к обоим этим частям, в результате чего последовательность разбивается на 4 части. Алгоритм применяется к каждой четвертинке и т.д. Разделение заканчивается, когда в каждой части остается 1 элемент.

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

Procedure Quick_Sort(n:word;Var a:massiv);

Procedure Sort1(l,r:word);

Var

w,x:integer;

i,j:word;

Begin

i:=l; j:=r;

x:=a[(l+r) div 2];

Repeat

While a[i]<x Do i:=i+1;

While a[j]>x Do j:=j-1;

If i<=j Then

begin

w:=a[i]; a[i]:=a[j]; a[j]:=w;

i:=i+1; j:=j-1

end

Until i>j;

If l<j Then Sort1(l,j);

If i<r Then Sort1(i,r);

End;{Sort1}

BEGIN

Sort1(1,n);

END;{Quick_Sort}

Порядок выполнения работы

1. Изучить теоретические сведения по теме: ”Алгоритмы обменных сортировок”.

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

3. Показать работающую программу преподавателю.

4. Ответить на контрольные вопросы.

Контрольные вопросы

1. Пузырьковая сортировка. Описание алгоритма и фрагмент программы.

2. Шейкерная сортировка. Описание алгоритма и фрагмент программы.

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

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

Лабораторная работа № 20

Реализация алгоритмов внешних сортировок при написании программы на Паскале

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

Краткие теоретические сведения

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

Метод простого слияния

Пусть в последовательном файле (ленте) имеется следующая информация:

31 42 09 29 37 01 12 06

Во внешних сортировках каждый проход состоит из фаз. В методе простого слияния существует 2 фазы: разделения и слияния. Для рассмотренного метода нужны 3 ленты. Исходная последовательность (А) разделяется на 2 ленты (В и С):

A: 31 42 09 29 37 01 12 06 –исходный файл

B: 31 42 09 29

C: 37 01 12 06

Затем выполняется фаза слияния: анализируются доступные на лентах В и С элементы и посылаются на ленту А в виде упорядоченных пар:

A: 31 37 01 42 09 12 06 29.

Теперь содержимое ленты А состоит из упорядоченных пар. Затем снова разделяется наполовину:

В: 31 37 01 42

С: 09 12 06 29.

Последовательность сливается в упорядоченные четверки.

А: 09 12 31 37 01 06 29 42.

 

Схематично метод простого слияния выглядит так:

Естественное слияние

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

A[L],A[L+1],…A[k],

такая, что:

A[L] A[L+1] …A[k],

A[L-1]>A[L],

A[k+1]<A[k].

Метод работает так: сначала первая серия посылается на ленту В, вторая- на ленту С, третья- на ленту В, четвертая на С и т.д. Первая серия с ленты В сливается с первой серией ленты С. В результате на ленте А куда сливаются эти серии появится 1-ая увеличенная серия.

Затем вторая серия ленты В сливается со второй серией ленты С и т.д. После выполнения всех вариантных слияний количество серий на ленте А окажется в двое меньше, чем в исходной последовательности. Затем снова разделение серий, снова слияние и т.д.

Многопутевое слияние

В этом методе исходная лента разделяется не на две, а на m лент (m>2).

Схематично метод простого слияния выглядит так (рис1.):

Рисунок 1 Многопутевое слияние

 

На рисунке 1- B1,B2, …, Bm соответственно 1,2,.., m –тая дополнительные ленты.

Алгоритм метода работает так: первая серия на ленте А при выполнении фазы разделения помещается на ленту В1, вторая серия-на ленту В2 и т.д., m- тая серия на ленту Вm. M+1 серия на ленту В1, M+2- на ленту В2 и т.д.

После выполнения фазы разделения происходит слияние всех первых серий каждой дополнительной ленты. Для организации слияния в ОП может быть организован массив из m элементов.

После выполнения первой фазы разделения на каждой из дополнительных лент будет размещено примерно ]N/m[ серий. После выполнения второй фазы разделения число серий на каждой ленте ]N/m[ /m.

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

Порядок выполнения работы

1. Изучить теоретические сведения по теме: ”Алгоритмы внешних сортировок”

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

3. Показать выполненное задание преподавателю.

4. Ответить на контрольные вопросы.

Контрольные вопросы

1. Понятие внешней сортировки. Виды сортировок.

2. Метод простого слияния. Описание алгоритма.

3. Естественное слияние. Описание алгоритма.

4. Многопутевое слияние.Описание алгоритма.

 

Лабораторная работа № 21