- •Вологодский государственный педагогический университет Факультет прикладной математики и компьютерных технологий Индивидуальное задание по исследованию алгоритмов Сортировки
- •Вариант задания
- •Обзор алгоритмов
- •Сортировка простым выбором
- •Быстрая сортировка с ограничением рекурсии
- •Случайный массив
- •Отсортированный массив
- •Обратно отсортированный массив
- •Сортировка простым выбором на языке Java
- •Быстрая сортировка с ограниченной рекурсией на языке Java
- •Число пересылок
- •Число сравнений ключа
- •Число пересылок
Вологодский государственный педагогический университет Факультет прикладной математики и компьютерных технологий Индивидуальное задание по исследованию алгоритмов Сортировки
Выполнил:
студент II курса факультета ПМ и КТ
Попов Максим Сергеевич
Принял:
Свердлов Сергей Залманович
Вологда
2011
Вариант задания
Вариант 20
Таблица 1. Вариант задания
Алгоритмы |
Сортировка простым выбором |
Сортировка методом Д.Шелла |
|
Быстрая сортировка с ограничением рекурсии |
|
|
|
Использование барьера |
Не используется |
|
|
Тип ключа |
Целый (16 разрядов) |
Тип данных |
Целый (16 разрядов) |
|
|
Исследуемые характеристики |
Время сортировки |
Число сравнений ключа |
|
Число пересылок |
|
|
|
Изменяемые величины |
Число элементов |
Параметры алгоритма |
|
|
|
Исследуемые варианты |
Случайный массив |
Отсортированный массив |
|
Обратно отсортированный массив |
Обзор алгоритмов
const
nmax = 5000;
type
tKey = integer;
tData = integer;
tItem = record
Key : tKey;
Data: tData;
end;
tArray=array[1..nmax] of tItem;
Сортировка простым выбором
procedure SelectSort(var a: tArray; n: integer);
var
i, j, jmin: integer;
buf: tItem;
begin
for i := 1 to n-1 do begin
jmin := i;
for j := 1 to i-1 do
if a[j].key > a[jmin].key then
jmin := j;
buf := a[i];
a[i] := a[jmin];
a[jmin] := buf;
end;
end.
Сортировка методом Д.Шелла
procedure ShellSort(var a: tArray; n: integer);
var
i, j, h: integer;
x: tItem;
begin
h:=13;
while h<n do
h:=3*h + 1;
h:=(h - 1) div 3;
repeat
h:=(h - 1) div 3;
for i:=h + 1 to n do begin
x:=a[i];
j:=i - h;
while (j > 0) and (x.key < a[j].key) do begin
a[j + h]:=a[j];
j:=j - h;
end;
a[j + h]:=x;
end;
until h <= 1;
end;
Быстрая сортировка с ограничением рекурсии
procedure QuickSort(var a: tArray; n: integer);
procedure Sort(L, R: integer);
var
i, j: integer;
x, y: tItem;
begin
while L < R do begin
i:=L; j:=R;
x:=a[(L + R) div 2];
repeat
while x.key > a[i].key do i:=i + 1;
while a[j].key > x.key do j:=j - 1;
if i <= j then begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
i:=i + 1; j:=j - 1;
end;
until i > j;
if i – L < R - j then begin
Sort(L, j);
l:=i;
end
else begin
Sort(i, R);
R:=j;
end;
end;
end;
begin
Sort(1, n);
end;