Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-12-12 | 189 |
5.00
из
|
Заказать работу |
|
|
Обзор алгоритмов
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;
Случайный массив
Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||
Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |
1601,836757 | 113,4477251 | 72,4017339 | |||||||
6402,887609 | 329,4280674 | 226,6895285 | |||||||
14361,43253 | 531,1959487 | 409,7542766 | |||||||
25499,92922 | 785,9783052 | 534,9147375 | |||||||
39851,71764 | 1045,06517 | 720,8894591 | |||||||
57324,3712 | 1314,571237 | 889,6958959 | |||||||
77883,43558 | 1579,657417 | 1070,716681 | |||||||
101667,0398 | 1850,444684 | 1233,883258 | |||||||
128585,2259 | 2130,315735 | 1421,656056 | |||||||
158523,8082 | 2364,401484 | 1601,547939 |
|
Отсортированный массив
Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||
Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |
1601,39662 | 19,0812573 | 14,8805805 | |||||||
6388,966313 | 69,9939788 | 74,3388895 | |||||||
14356,22485 | 150,6567637 | 149,1735951 | |||||||
25544,21216 | 210,476764 | 198,9575831 | |||||||
39835,13891 | 280,2481636 | 276,0115434 | |||||||
57367,18554 | 347,0238535 | 357,8946275 | |||||||
78021,87746 | 463,4552023 | 415,9816192 | |||||||
101943,1232 | 536,5044669 | 475,8422242 | |||||||
128935,1281 | 581,8522369 | 522,3087196 | |||||||
159144,7316 | 658,2673603 | 608,4132491 |
Обратно отсортированный массив
Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||
Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |
1587,29439 | 61,095304 | 21,1533577 | |||||||
6323,765326 | 189,7683288 | 84,3938507 | |||||||
14225,0402 | 311,5236291 | 170,7748294 | |||||||
25295,59026 | 408,3120362 | 226,2148742 | |||||||
39505,04711 | 550,1877857 | 318,2928401 | |||||||
56842,79165 | 700,0719592 | 408,6996313 | |||||||
77417,90677 | 796,435305 | 471,1712062 | |||||||
101143,9112 | 953,2062336 | 537,6662122 | |||||||
127890,5549 | 1082,117967 | 591,3859857 | |||||||
158054,8388 | 1210,459579 | 691,4279534 |
Число сравнений ключа
Число сравнений ключа
Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией
|
Сортировка простым выбором
Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией
Число пересылок
Сортировка простым выбором: для поиска одного элемента с наибольшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую последовательность.
Сортировка методом Шелла: используется сортировка вставками, применяя принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.
Быстрая сортировка с ограниченной рекурсией: выбирается для сравнения один элемент х, отыскивается слева первый элемент, который не меньше х, а справа первый элемент, который не больше х. Найденные элементы меняются местами. После первого же прохода все элементы, которые меньше х, будут стоять слева от х, а все элементы, которые больше х, - справа от х. С двумя половинами массива поступают точно также. Продолжая деление этих половин до тех пор пока не останется в них по 1 элементу.
На языке Java
protected static void Sort(tItem a[], int L, int R)
{
tItem x;
tItem y;
int i;
int j;
while (L < R)
{
x = a[(L + R) / 2];
i = L; j = R;
do
{
while (a[i].Key < x.key) { i++; };
w hile (x.key < a[j].Key) { j--; };
if (i <= j)
{
y = a[i];
a[i] = a[j];
a[j] = y;
i++;
j--;
}
} while (i <= j);
if (j - L < R - i)
{
Sort(a, L, j);
L = i;
}
Else
{
Sort(a, i, R);
R = j;
}
}
}
static void QuickSort(tItem a[], int n)
{
Sort(a, 1, n);
}
Сортировка простым выбором
Число сравнений ключа:
Число пересылок:
;
Параметрах алгоритма
Последовательность предложенная Кнутом: все значения kk = 3*kk + 1
Последовательность предложенная Хиббардом: все значения ; такая последовательность шагов приводит к алгоритму сложностью O(N3 / 2);
Последовательность предложенная Седжвиком: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: O(n7 / 6), а в худшем случае порядка O(n4 / 3).
Число сравнений ключа
Кол-во элементов: | Кнут | Хиббард | Седжвик | ||||||
Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | |
Время
|
Кол-во элементов: | Кнут | Хиббард | Седжвик | ||||||
Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | |
1,135 | 0,181 | 0,648 | 1,237 | 0,391 | 0,762 | 1,586 | 0,075 | 0,954 | |
3,291 | 0,747 | 1,888 | 3,619 | 1,325 | 2,065 | 4,028 | 0,803 | 2,557 | |
5,426 | 1,507 | 3,134 | 5,824 | 2,398 | 3,581 | 6,384 | 1,462 | 3,802 | |
7,795 | 2,202 | 3,955 | 8,324 | 3,365 | 4,846 | 9,029 | 2,116 | 5,192 | |
10,387 | 2,808 | 5,516 | 11,093 | 4,692 | 5,97 | 11,725 | 3,091 | 6,808 | |
12,887 | 3,471 | 7,044 | 13,913 | 5,414 | 8,039 | 14,641 | 3,845 | 8,607 | |
15,838 | 4,664 | 7,257 | 16,51 | 6,541 | 9,159 | 17,237 | 4,605 | 10,314 | |
18,513 | 5,394 | 9,56 | 19,652 | 7,561 | 10,778 | 20,361 | 5,42 | 12,572 | |
21,442 | 5,839 | 10,843 | 22,913 | 9,196 | 11,744 | 23,264 | 6,293 | 13,089 | |
24,214 | 6,576 | 11,095 | 25,846 | 10,388 | 13,684 | 26,407 | 7,03 |
Число пересылок
Кол-во элементов: | Кнут | Хиббард | Седжвик | ||||||
Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсоритрованный массив | |
Число сравнений ключа
Время
Число пересылок
|
Вывод: В результате исследования алгоритмов сортировки «Простым выбором», «Сортировки методом Д.Шелла» и «Быстрой сортировки с ограниченной рекурсией» показало, что Быстрая сортировка в лучшем случае работает быстрее других, а в худшем так же как и сортировка Выбором и сортировка Шелла. Сортировка Простым выбором работает всех медленнее.
Обзор алгоритмов
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;
Случайный массив
Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||
Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |
1601,836757 | 113,4477251 | 72,4017339 | |||||||
6402,887609 | 329,4280674 | 226,6895285 | |||||||
14361,43253 | 531,1959487 | 409,7542766 | |||||||
25499,92922 | 785,9783052 | 534,9147375 | |||||||
39851,71764 | 1045,06517 | 720,8894591 | |||||||
57324,3712 | 1314,571237 | 889,6958959 | |||||||
77883,43558 | 1579,657417 | 1070,716681 | |||||||
101667,0398 | 1850,444684 | 1233,883258 | |||||||
128585,2259 | 2130,315735 | 1421,656056 | |||||||
158523,8082 | 2364,401484 | 1601,547939 |
Отсортированный массив
Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||
Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |
1601,39662 | 19,0812573 | 14,8805805 | |||||||
6388,966313 | 69,9939788 | 74,3388895 | |||||||
14356,22485 | 150,6567637 | 149,1735951 | |||||||
25544,21216 | 210,476764 | 198,9575831 | |||||||
39835,13891 | 280,2481636 | 276,0115434 | |||||||
57367,18554 | 347,0238535 | 357,8946275 | |||||||
78021,87746 | 463,4552023 | 415,9816192 | |||||||
101943,1232 | 536,5044669 | 475,8422242 | |||||||
128935,1281 | 581,8522369 | 522,3087196 | |||||||
159144,7316 | 658,2673603 | 608,4132491 |
|
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!