4.Исследование программной реализации простых алгоритмов сортировки:
4.1. Примеры пошаговой работы:
Сортировка простыми включениями |
Шейкер-сортировка |
9 6 8 3 8 3 0 6 9 8 3 8 3 0 6 8 9 3 8 3 0 6 8 3 9 8 3 0 6 3 8 9 8 3 0 3 6 8 9 8 3 0 3 6 8 8 9 3 0 3 6 8 8 3 9 0 3 6 8 3 8 9 0 3 6 3 8 8 9 0 3 3 6 8 8 9 0 3 3 6 8 8 0 9 3 3 6 8 0 8 9 3 3 6 0 8 8 9 3 3 0 6 8 8 9 3 0 3 6 8 8 9 0 3 3 6 8 8 9
|
1 6 0 6 8 1 0
0 1 0 6 6 1 8 0 0 1 1 6 6 8 0 0 1 1 6 6 8
|
4.2. Зависимость количества сравнений, обменов и их суммы исследуемых алгоритмов сортировки от размерности задачи n для прямого, обратного, случайного и равного расположения элементов в массиве:
Таблица 1 Сортировка простыми включениями, массив упорядочен случайно
n |
5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
Сравнения |
6 |
27 |
70 |
114 |
158 |
244 |
291 |
407 |
468 |
535 |
Обмен |
4 |
20 |
60 |
97 |
136 |
217 |
259 |
369 |
426 |
488 |
Сумма |
10 |
47 |
130 |
211 |
294 |
461 |
550 |
776 |
894 |
1023 |
Таблица 2 Сортировка простыми включениями, массив упорядочен по возрастанию
n |
5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
Сравнения |
4 |
9 |
14 |
19 |
24 |
29 |
34 |
39 |
44 |
49 |
Обмен |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Сумма |
4 |
9 |
14 |
19 |
24 |
29 |
34 |
39 |
44 |
49 |
Таблица 3 Сортировка простыми включениями, массив упорядочен по убыванию
n |
5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
Сравнения |
10 |
45 |
99 |
182 |
289 |
420 |
554 |
736 |
913 |
1137 |
Обмен |
8 |
43 |
91 |
171 |
274 |
400 |
528 |
706 |
878 |
1097 |
Сумма |
18 |
88 |
190 |
353 |
563 |
820 |
1082 |
1442 |
1791 |
2234 |
Таблица 4 Шейкер-сортировка, массив упорядочен случайно
n |
5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
Сравнения |
9 |
31 |
81 |
144 |
194 |
298 |
415 |
566 |
645 |
938 |
Обмен |
7 |
17 |
48 |
102 |
129 |
202 |
276 |
385 |
450 |
642 |
Сумма |
16 |
48 |
129 |
246 |
323 |
500 |
691 |
951 |
1095 |
1580 |
Таблица 5 Шейкер-сортировка, массив упорядочен по возрастанию
n |
5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
Сравнения |
4 |
9 |
14 |
19 |
24 |
29 |
34 |
39 |
44 |
49 |
Обмен |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Сумма |
4 |
9 |
14 |
19 |
24 |
29 |
34 |
39 |
44 |
49 |
Таблица 6 Шейкер-сортировка, массив упорядочен по убыванию
n |
5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
Сравнения |
10 |
42 |
105 |
189 |
300 |
435 |
595 |
779 |
989 |
1224 |
Обмен |
9 |
37 |
98 |
177 |
277 |
387 |
542 |
702 |
901 |
1115 |
Сумма |
19 |
79 |
203 |
366 |
577 |
822 |
1137 |
1481 |
1890 |
2339 |
Рисунок 1 – График,при
котором исходный массив распределен
хаотически
Рисунок 2 – График, при
котором исходный массив распределен
по возрастанию
Рисунок 3 – График, при
котором исходный массив распределен
по убыванию