Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией
Вологодский государственный педагогический университет
Факультет прикладной математики и компьютерных технологий
Индивидуальное задание по исследованию алгоритмов Сортировки
Выполнил:
студент 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;
Случайный массив
| Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||||
| Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |||
| 500 | 1601,836757 | 124750 | 1497 | 113,4477251 | 5957 | 8022 | 72,4017339 | 5485 | 3576 | ||
| 1000 | 6402,887609 | 499500 | 2997 | 329,4280674 | 14637 | 19705 | 226,6895285 | 11617 | 7797
| ||
| 1500 | 14361,43253 | 1124250 | 4497 | 531,1959487 | 23253 | 33046 | 409,7542766 | 17808 | 12162 | ||
| 2000 | 25499,92922 | 1999000 | 5997 | 785,9783052 | 33325 | 45641 | 534,9147375 | 24202 | 16926 | ||
| 2500 | 39851,71764 | 3123750 | 7497 | 1045,06517 | 45258 | 59638 | 720,8894591 | 33719 | 21534 | ||
| 3000 | 57324,3712 | 4498500 | 8997 | 1314,571237 | 58979 | 74392 | 889,6958959 | 38952 | 26658 | ||
| 3500 | 77883,43558 | 6123250 | 10497 | 1579,657417 | 64949 | 91423 | 1070,716681 | 44815 | 31608 | ||
| 4000 | 101667,0398 | 7998000 | 11997 | 1850,444684 | 79354 | 104202 | 1233,883258 | 55370 | 37080 | ||
| 4500 | 128585,2259 | 10122750 | 13497 | 2130,315735 | 91413 | 118119 | 1421,656056 | 58721 | 42264 | ||
| 5000 | 158523,8082 | 12497500 | 14997 | 2364,401484 | 105132 | 133656 | 1601,547939 | 72546 | 47817 | ||
Отсортированный массив
| Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||||
| Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |||
| 500 | 1601,39662 | 124750 | 1497 | 19,0812573 | 2321 | 4642 | 14,8805805 | 4023 | 771 | ||
| 1000 | 6388,966313 | 499500 | 2997 | 69,9939788 | 4821 | 9642 | 74,3388895 | 9045 | 1563 | ||
| 1500 | 14356,22485 | 1124250 | 4497 | 150,6567637 | 8457 | 16914 | 149,1735951 | 14962 | 2970 | ||
| 2000 | 25544,21216 | 1999000 | 5997 | 210,476764 | 11457 | 22914 | 198,9575831 | 20163 | 3219 | ||
| 2500 | 39835,13891 | 3123750 | 7497 | 280,2481636 | 14457 | 28914 | 276,0115434 | 26506 | 4614 | ||
| 3000 | 57367,18554 | 4498500 | 8997 | 347,0238535
| 17457 | 34914 | 357,8946275 | 32939 | 6012 | ||
| 3500 | 78021,87746 | 6123250 | 10497 | 463,4552023 | 22864 | 45728 | 415,9816192 | 38793 | 6396 | ||
| 4000 | 101943,1232 | 7998000 | 11997 | 536,5044669 | 26364 | 52728 | 475,8422242 | 44563 | 6753 | ||
| 4500 | 128935,1281 | 10122750 | 13497 | 581,8522369 | 29864 | 59728 | 522,3087196 | 51408 | 8010 | ||
| 5000 | 159144,7316 | 12497500 | 14997 | 658,2673603 | 33364 | 66728 | 608,4132491 | 58380 | 9564 | ||
Обратно отсортированный массив
| Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||||
| Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |||
| 500 | 1587,29439 | 124750 | 1497 | 61,095304 | 4627 | 6950 | 21,1533577 | 3778 | 1512 | ||
| 1000 | 6323,765326 | 499500 | 2997 | 189,7683288 | 10800 | 15625 | 84,3938507 | 8561 | 3072 | ||
| 1500 | 14225,0402 | 1124250 | 4497 | 311,5236291 | 16716 | 25172 | 170,7748294 | 14229 | 5223 | ||
| 2000 | 25295,59026 | 1999000 | 5997 | 408,3120362 | 20634 | 32088 | 226,2148742 | 19128 | 6222 | ||
| 2500 | 39505,04711 | 3123750 | 7497 | 550,1877857 | 29853 | 44322 | 318,2928401 | 25333 | 8304 | ||
| 3000 | 56842,79165 | 4498500 | 8997 | 700,0719592 | 37151 | 54601 | 408,6996313 | 31498 | 10503 | ||
| 3500 | 77417,90677 | 6123250 | 10497 | 796,435305 | 37866 | 60724 | 471,1712062 | 37030 | 11694 | ||
| 4000 | 101143,9112 | 7998000 | 11997 | 953,2062336 | 49127 | 75486 | 537,6662122 | 42587 | 12726 | ||
| 4500 | 127890,5549 | 10122750 | 13497 | 1082,117967 | 55114 | 84977 | 591,3859857 | 49104 | 14859
| ||
| 5000 | 158054,8388 | 12497500 | 14997 | 1210,459579 | 57883 | 91241 | 691,4279534 | 55831 | 17010 | ||
Число сравнений ключа
Число сравнений ключа
Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией
Сортировка простым выбором
Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией
Число пересылок
Сортировка простым выбором: для поиска одного элемента с наибольшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую последовательность.
Сортировка методом Шелла: используется сортировка вставками, применяя принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.
Быстрая сортировка с ограниченной рекурсией: выбирается для сравнения один элемент х, отыскивается слева первый элемент, который не меньше х, а справа первый элемент, который не больше х. Найденные элементы меняются местами. После первого же прохода все элементы, которые меньше х, будут стоять слева от х, а все элементы, которые больше х, - справа от х. С двумя половинами массива поступают точно также. Продолжая деление этих половин до тех пор пока не останется в них по 1 элементу.
Дата добавления: 2021-01-20; просмотров: 42; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!