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

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

Выбирается любой произвольный элемент массива, далее массив просматривается слева направо до тех пор пока не будет найден элемент больший выбранного; а затем просмотрим его справа налево, пока не найдем элемент меньший выбранного. Найденные элементы поменяем местами. Затем продолжим процесс “просмотра с обменом”, пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими выбранного элемента; и правую - с большими ключами. Описанный алгоритм применяется к обоим этим частям, в результате чего последовательность разбивается на 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

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

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