Файл: Алгоритмы сортировки данных (Сущность понятия «алгоритм» и его элементы.pdf

Задания:
1. Сортировка списка простыми вставками.
2. Сортировка слиянием.
3. Сортировка Хоара.
4. Расщепление списка на минимальный элемент и список из
остальных элементов.
5. Объединение двух множеств, представленных списками.

Для решения задач мной использовался следующий модуль:

===================================начало===================================
{ модуль, содержащий ряд процедур и функций, которые будут;
использоваться в решении задач лабораторной работы. }
unit List_for_Sort;

interface

Type PList = ^List;
List = record
inf: smallint;
next: PList;
end;
{ Процедура создает неупорядоченный список. }
Procedure Create_List(Var Head: PList);
{ Процедура удаляет список. }
Procedure Destroy_List(Head: PList);
{ Процедура добавляет элемент в список за элементом;
меньшим в списке. }
Procedure Include(Var Head: PList; Adding: PList);
{ Процедура выводит на экран список. }
Procedure Show_List(Head: PList);
{ Функция определения длины списка. }
Function List_Len(Head: PList): byte;

implementation

Procedure Create_List(Var Head: PList);
Var
tmp: PList;
Max, i: byte;
begin
{ Вводим количество элементов. }
Write('Enter number elements of list ');
Readln(Max); { Считываем введенное значение. }
Head:=nil;
for i := 1 to Max do { Цикл для создания списка. }
begin
New(tmp); { Создаем новый элемент. }
{ Устанавливаем ссылку с созданного элемента на голову. }
tmp^.next:=Head;
{ Заново устанавливаем голову. }
Head:=tmp;
{ Заполняем информационную часть списка. }
Head^.inf:= - 13 + random(27);
end;
end;
Procedure Destroy_List(Head: PList);
Var
tmp: PList;
begin
{ С помощью цикла доходим до конца списка поэлементно уничтожая
его. }
while Head <> nil do { Условие выхода из цикла. }
begin
tmp:=Head^.next; { Запоминаем элемент, следующий за
головой, }
Dispose(Head); { уничтожаем голову, }
Head:=tmp; { устанавливаем голову. }
end;
end;
Procedure Show_List(Head: PList);
begin
{ Используем цикл, с условием выхода: конец списка, - ;
для вывода списка на экран. }
while Head <> nil do
begin
write(Head^.inf:4); { Собственно - сам вывод. }
Head:=Head^.next; { Переходим на следующий элемент. }
end;
end;
Procedure Include(Var Head: PList; Adding: PList);
Var
tmp1, tmp2: PList;
begin
{ если дан пустой список то добавляемый элемент становится
начальным элементом нового списка. }
if Head = nil then
begin
Adding^.next:=nil;
Head:=Adding;
Exit; { подпрограмма в этом случае
завершается. }
end;
tmp1:=Head;
{ если добавляемый меньше, либо равен первому элементу
то он добавляется перед первым элементом и становится
первым. }
If Adding^.inf<=Head^.inf then
begin
Head:=Adding;
Adding^.next:=tmp1;
Exit;
end;
{ если добавляемый элемент находится в диапазоне чисел списка,
то находим число в списке равное либо большее добавляемого. }
While (Adding^.inf > tmp1^.inf) and (tmp1^.next <> nil) do
begin
tmp2:=tmp1;
tmp1:=tmp1^.next;
end;
{ если добавляемый элемент имеет наибольшее значение среди
элементов списка, то он добавляется в конец списка. }
If tmp1^.next=nil then
begin
tmp1^.next:=Adding;
Adding^.next:=nil;
Exit; { подпрограмма в этом случае
завершается. }
end;
{ после того как было найдено число большее либо равное
добавляемого, присоединяем элемент перед ним. }
tmp2^.next:=Adding;
Adding^.next:=tmp1;
end;
Function List_Len(Head: PList): byte;
Var
n: byte;
begin
{ Для начала устанавливаем длину списка равной нулю. }
n:=0;
{ Циклом добираемся до конца списка, считая элементы. }
while Head <> nil do
begin
Head:=Head^.next; { Переходим на следующий элемент. }
inc(n); { Увеличиваем переменную на единицу. }
end;
List_Len:=n; { Присваиваем значение функции. }
end;
end.
===================================конец====================================

---

Задача №1

==================================начало===================================

program Lab_3_N_1;

{$APPTYPE CONSOLE}

uses
SysUtils,
List_for_Sort in '...\List_for_Sort.pas';
Var
Head: PList;
{ Процедура выполняющая сортировку списка методом простых;
вставок. }
Procedure Simple_Insert(Head: PList);
Var
tmp1: PList;
{ Подпроцедура которая и выполняет рекурсивную сортировку. }
Procedure Sorting(Var Head: PList);
Var
tmp: PList;
x, x1: smallint;
begin
Head:=Head^.next;
{ Условие выхода из рекурсии. }
if Head = nil then Exit;
tmp:=tmp1;
{ Ищем, куда необходимо вставить элемент, то есть доходим;
до элемента большего, либо равного сравниваемого. }
while Head^.inf > tmp^.inf do tmp:=tmp^.next;
x:=tmp^.inf;
tmp^.inf:=Head^.inf;
{ Вставляем элемент на новое место и сдвигаем остальные до;
места, откуда убрали вставленный. }
while tmp^.next <> Head^.next do
begin
tmp:=tmp^.next;
x1:=tmp^.inf;
tmp^.inf:=x;
x:=x1;
end;
Sorting(Head);
end;
begin
{ Одноэлементные и пустые списки сортировки не требуют. }
if (Head = nil)or (Head^.next = nil) then exit;
tmp1:=Head;
Sorting(Head);
end;

begin
Randomize;
Create_List(Head);
Write('List : ');
Show_List(Head);
Readln;
Simple_Insert(Head);
Write('Sorting: ');
Show_List(Head);
Readln;
Destroy_List(Head);
end. ===================================конец====================================

Тестовый пример:
Enter number elements of list 4
List: -7 4 2 -8
Sorting: -8 -7 2 4

Задача №2

===================================начало===================================
program Lab_3_N_2;

{$APPTYPE CONSOLE}

uses

SysUtils,
List_for_Sort in '..\List_for_Sort.pas';

Var Root, Root_Sort: PList;
{ Функция слияния списков Lst1 и Lst2 в один упорядоченный. }
Function Merge(Lst1, Lst2 : PList) : PList;
Var tmp21, tmp2 : PList;
begin
New(tmp21);
tmp2:=tmp21;
{ Чтобы из двух списков создать один, нужно на каждой итерации
выбирать меньший из первых элементов и присоединять его к результату. }
while (Lst1 <> nil) or (Lst2 <> nil) do
if (Lst2 = nil) or ((Lst1 <> nil) and (Lst1^.inf < Lst2^.inf)) then
begin
tmp2^.next:=Lst1;
tmp2:=Lst1;
Lst1:=Lst1^.next;
tmp2^.next:=nil;
end
else
begin
tmp2^.next:=Lst2;
tmp2:=Lst2;
Lst2:=Lst2^.next;
tmp2^.next:=nil;
end;
Merge:=tmp21^.next;
Dispose(tmp21);
end;

Function Sort(Root : PList) : PList;
{ Функция разбивает список Root пополам и передает в
функцию слияния. }
Var len, i: byte;
tmp211, tmp212 : PList;
begin
if (Root = nil) or (Root^.next = nil) then Sort:=Root
{Пустые и одноэлементные списки сортировки не требуют}
else begin
tmp211:=Root;
len:=List_Len(Root) div 2 - 1;
for i:=1 to len do Root:=Root^.next;
tmp212:=Root^.next;
Root^.next:=nil;
{Теперь нужно упорядочить каждую часть и слить в один при
помощи функции слияния. Т.к. части в общем случае не упорядоченные,
разобьем каждую из них при помощи этой же функции}
Sort:=Merge(Sort(tmp211), Sort(tmp212));
end;
end;

begin { Основная программа. }
Randomize;
Create_List(Root);
Write('List: ');
Show_List(Root);
Writeln;
Root_Sort:=Sort(Root);
Write('Sorting: ');
Show_List(Root_Sort);
readln;
end.

---

===================================конец====================================

Тестовый пример:
Enter number elements of list 3
List: 11 -13 12
Sorting: -13 11 12

Задача №3

===================================начало===================================
program Lab_3_N_3;

{$APPTYPE CONSOLE}

uses
SysUtils,
List_for_Sort in '..\List_for_Sort.pas';

Var Root: PList;

procedure Quick_Sort(Var Root: PList);
{ Процедура сортирует список Root методом Хоара. }
Var tmp1, tmp2, tmp3: PList;
begin
if not((Root = nil) or (Root^.next = nil)) then
begin
tmp2:=Root; { базовый элемент, относительно которого меняем элементы. }
tmp1:=Root;
while tmp1^.next <> nil do
begin
{ Все элементы меньшие базового поместим в начало списка. }
if tmp2^.inf > tmp1^.next^.inf then
begin
tmp3:=tmp1^.next;
tmp1^.next:=tmp3^.next;
tmp3^.next:=Root;
Root:=tmp3;
end
else tmp1:=tmp1^.next;
end;
{ После этого хотя бы один элемент окажется на своем месте; }
{ Разобьем список на два в первом окажутся элементы с;
первого по базовый включительно, во втором - остальные. }
tmp1:=tmp3^.next;
tmp3^.next:=nil;
{ Сортируем каждую часть отдельно тем же алгоритмом. }
Quick_Sort(Root);
Quick_Sort(tmp1);
{ Соединим две части списка. }
tmp3:=Root;
while tmp3^.next <> nil do tmp3:=tmp3^.next;
tmp3^.next:=tmp1;
end;
end;

begin { Основная программа. }
Randomize;
Create_List(Root);
Write('List: ');
Show_List(Root);
Writeln;
Quick_Sort(Root);
Write('Sorting: ');
Show_List(Root);
Destroy_List(Root);
readln;
end.

===================================конец====================================
Тестовый пример:
Enter number elements of list 6
List: 7 -4 12 11 1
Sorting: -4 1 7 11 12

Задача №4

===================================начало===================================
program Lab_3_N_4;

{$APPTYPE CONSOLE}

uses
SysUtils,
List_for_Sort in '..\List_for_Sort.pas';

Var Root1, Root2, Root3 : PList;
{ Процедура разделяет список Root на два Min и Other. }
Procedure Find_Min(Var Root, Min, Other : PList);
Var tmp1, tmp2 : PList;
MinInt: smallint;
begin
{ Проверка на пустые и одноэлементные списки. }
if Root = nil then exit;
if Root^.next = nil then begin
min := Root;
Root := nil;
Other := nil;
exit;
end;
{ Ищем минимальный элемент. }
tmp1 := Root^.next;
MinInt := Root^.inf;
while (tmp1 <> nil) do
if MinInt > tmp1^.inf then begin
MinInt := tmp1^.inf;
tmp1 := tmp1^.next;
end
else tmp1 := tmp1^.next;
{ Чтобы избавится от лишних операций с головой добавим ее искусственно. }
new(tmp1);
tmp1^.inf := 32767;
tmp1^.next := Root;
Root := tmp1;
{ Удалим все элементы равные минимальному. }
while tmp1^.next <> nil do
if tmp1^.next^.inf = MinInt then begin
tmp2 := tmp1^.next;
tmp1^.next := tmp2^.next;
Dispose(tmp2);
tmp1 := tmp1^.next;
end
else tmp1 := tmp1^.next;
{ Распределяем выходные данные. }
Other := Root^.next;

Dispose(Root);
New(Min);
Min^.inf := MinInt;
Min^.next := nil;
Root := nil;
end;
begin { Основная программа. }
Create_List(Root1);
Write('List : ');
Show_List(Root1);
Writeln;
Find_Min(Root1, Root2, Root3);
Write('Min : ');
Show_List(Root2);
Writeln;
Write('Other : ');
Show_List(Root3);
readln;
Destroy_List(Root1);
Destroy_List(Root2);
Destroy_List(Root3);
end.

---

===================================конец====================================

Тестовый пример:
Enter number elements of list 4
List: -8 10 -13 -12
Min : -13
Other: -8 10 -12

Задача №5

===================================начало===================================
program Lab_3_N_5;

{$APPTYPE CONSOLE}

uses
SysUtils,
List_for_Sort in '..\List_for_Sort.pas';

Var Root1, Root2, Root3: PList;
{ Процедура объединения множеств а и Head2.
Результат выполнения передается в Head3. }
procedure Unite_List(Head1, Head2: PList; Var Head3: PList);
Var tmp1, tmp2, tmp3: PList;
begin
{ Искусственно создадим первый элемент. Т. к. функция Include
не работает с пустыми списками. }
New(Head3);
Head3^.next:=nil;
{ Объединение множества и пустого множества есть пустое множество. }
if (Head1 <> nil) or (Head2 <> nil) then
begin
if Head1^.inf < Head2^.inf then begin
tmp2:=Head2;
end
else begin
tmp1:=Head2;
tmp2:=Head1;
end;
{ Просканируем весь список. }
while (tmp1 <> nil) and (tmp2 <> nil) do
begin
while (tmp1 <> nil) and (tmp2^.inf > tmp1^.inf) do
tmp1:=tmp1^.next;
if tmp1 = nil then break;
{ В данный момент tmp2^.inf <= tmp1^.inf
если "равно" то tmp2^.inf должно быть в объединении множеств
если нет - то переходим к след элементу списка tmp2. }
if tmp2^.inf = tmp1^.inf then Include(Head3,tmp2);
tmp2:=tmp2^.next;
end;
end;
{ Удалим первый ненужный элемент и установим голову на следующий. }
tmp3:=Head3;
Head3:=Head3^.next;
Dispose(tmp3);
{ При таком алгоритме каждое множество обходится не более одного раза. }
end;

begin { Основная программа. }
Randomize;
Create_List(Root1);
Create_List(Root2);
Write('List 1: ');
Show_List(Root1);
Writeln;
Write('List 2: ');
Show_List(Root2);
Writeln;
Unite_List(Root1, Root2, Root3);
Write('Unite: ');
Show_List(Root3);
readln;
Destroy_List(Root1);
Destroy_List(Root2);
Destroy_List(Root3);
end.
===================================конец====================================
Тестовый пример:
Enter number elements of list 3
Enter number elements of list 3
List 1: -4 1 0
List 2: 10 4 4
Unite:

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

ЗАКЛЮЧЕНИЕ

По результатам замеров производительности методов можно сделать следующие выводы:

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

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

---