Реферат по дициплине: «Структуры данных и алгоритмы»

МИИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН

САМАРКАНДСКИЙ ФИЛИЛАЛ

ТАШКЕНТСКОГО УНИВЕРСИТЕТА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ АЛ-ХОРЕЗМИ




Кафедра Информационные технологии

Самостоятельная работа №2

РЕФЕРАТ
По дициплине: «Структуры данных и алгоритмы»
Выполнил: студентка группы: С 20-03б КИ. Хайдарова М.
Принял: преподаватель Хужаяров И.Ш.
Самарканд 2022


Тема: Методы сортировки и их применение.
ПЛАН:
1.Алгоритмы сортировок.
2.Эффективность методов.
3.Графический интерфейс.
4.Заключение.
5.Литература.

Алгоритмы сортировок

1. Сортировка методом обмена

Алгоритм сортировки обменами основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.
Мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причём вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу(см. табл. 1). Такой метод широко известен под именем «пузырьковая сортировка». В своем простейшем виде он представлен в программе 1.
Таблица 1.
Пример пузырьковой сортировки

44	12	12	12	12	12	12	12
66	44	13	13	13	13	13	13
23	66	44	23	23	23	23	23
45	23	66	44	44	44	44	44
12	45	23	66	66	45	45	45
67	12	45	45	45	66	66	66
13	67	67	67	67	67	67	67
88	88	88	88	88	88	88	88

Программа 1. Процедура ExchangeSort

procedure ExchangeSort( var A : mas );
var
x : integer;
begin
for i := N downto 2 do
for j := 2 to i do
if A[j] < A[j - 1] then
begin
x := A[j];
A[j] := A[j - 1];
A[j - 1] := x;
end;
1.2 Сортировка с помощью выбора
Этот прием основан на следующих принципах:

1. 
   Выбираем элемент с наименьшим ключом.
   
2. 
   Передвигаем на 1 позицию направо элементы, больше выбранного элемента.
   
3. 
   Вставляем выбранный элемент в нужную позицию.
   
4. 
   Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один , самый большой элемент.
   

Процесс работы этого метода приведен в таблице 2. Реализация этого алгоритма в программе 2.
Таблица 2.
Пример сортировки вставками

44	12	12	12	12	12	12	12
66	44	13	13	13	13	13	13
23	66	44	23	23	23	23	23
45	23	66	44	44	44	44	44
12	45	23	66	66	45	45	45
67	12	45	45	45	66	66	66
13	67	67	67	67	67	67	67
88	88	88	88	88	88	88	88

Программа 2. Процедура InsertSort
procedure InsertSort( var A : mas );
var
i, k : Integer;
x : integer;
begin
for i := 2 to N do
begin
k := i;
x := A[i];
while (A[k - 1] > x) do
begin
A[k] := A[k - 1];
k := k - 1;
end;
A[k] := x;
end;

3. Сортировка методом Хоара

Ч. Хоар изобрел алгоритм сортировки массива и назвал его метод быстрой сортировки(Quicksort).
В Quicksort исходят из того соображения, что для достижения наилучшей Эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь нечто действительно поучительное.
Давайте, попытаемся воспользоваться таким алгоритмом: выберем наугад какой-либо элемент(назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент   >x, затем будем просматривать массив справа, пока не встретим   Программа 3. Функция Partition
function Partition( var A : mas; l, r : Integer; x : integer ) : Integer;
var
i, j : Integer;
t : integer;
begin
i := l - 1;
j := r + 1;
repeat
j := j - 1;
until x >= A[j];
repeat
i := i + 1;
until A[i] >= x;
if i < j then
begin
t := A[i];
A[i] := A[j];
A[j] := t;
end;
until i >= j;
Partition := j;
end;
Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям, затем к частям частей, и так до тех пор, пока каждая их частей не будет состоять из одного-единственного элемента. Эти действия описываются программой 4.
Программа 4. Процедура RecoursiveQuicksort
procedure RecoursiveQuick( var A : mas; l, r : Integer );
var
m : Integer;
begin
if l < r then
begin
m := Partition(A, l, r, A[(l + r) div 2]);
RecoursiveQuick(A, l, m);
RecoursiveQuick(A, m + 1, r);
end;

3. Сортировка методом Уильямса-Флойда

Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма "пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого "пирамидой". Алгоритм не требует дополнительной памяти. Высокая эффективность алгоритма и гарантированная надежность для самого "худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.
Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду "пирамиды". На втором этапе осуществляется сортировка "пирамиды".
Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:
X[1]
X[2] X[3]
X[4] X[5] X[6 ] X[7]
X[8] X[9] ................................
Структура дерева имеет логический характер - в памяти компьютера все элементы массива всеравно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка X[2i] и X[2i+1], где i - индекс данного элемента. Элементы массива, являющегося "пирамидой", обладают дополнительными свойствами:
1. Любой элемент пирамиды X[i] не меньше, чем его элементы-потомки X[2i] и X[2i+1] (соответственно первый элемент обладает максимальным значением):
X[i] >= X[2i],
X[i] >= X[2i+1]
2. Любая подпоследовательность элементов вида X[n\2+1], X[n\2+2], ... X[n] также является пирамидой, обладающей свойствами 1 и 2. После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.
В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и "укоротим" массив на 1 элемент с "хвост а". Наибольший элемент массива окажется последним. "Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент X[1] и его потомки - X[2] и X[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент X[1] и наибольший из потомков: max(X[2], X[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор, пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом. Реализация этого алгоритма в программе 5.
Программа 5. Процедура PiramidaSort
Procedure PiramidaSort(var A: mas);
Var t, k, i, Y: Integer;
Begin
For i := 2 to N do { создание структуры бинарного дерева-"пирамиды" }
begin
t := i;
while t <> 1 do
begin k := t div 2;
If A[k] >= A[t] then t := 1
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k;
end;
For i := N-1 downto 1 do { сортировка массива-"пирамиды" }
begin
Y:=A[i+1]; A[i+1]:=A[1]; A[1]:=Y;
t := 1;
While t <> 0 do
begin
k := t+t;
If k > i then t := 0
else
begin
If k < i then If A[k+1] > A[k] then k := k+1;
If A[t] >= A[k] then t := 0
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k
end