Сортировка Шелла
Идея метода заключается в сравнении разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно step или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных
друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние step сокращается на step/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на step=1 проход по массиву происходит в последний раз.
В процессе работы программы происходит последовательное создание и заполнение случайными числами 1000 массивов для каждой заданной длины. Далее происходит сортировка данных.
Помимо этого, фиксируется количество операций (перестановок и сравнений) в специально созданные переменные.
Полный код программы представлен в приложении Б. Результат работы программы представлен на рисунке 2.2.1.
Рисунок 2.2.1 - Результат работы программы 2
В консольном выводе представляется размерность каждой тысячи массивов, среднее значение от суммы операций, а также среднее время выполнения сортировки.
Таблица 3 представляет собой таблицу со значениями длины массивов и средними значениями количества операций.
Таблица 3 - Средние значения количества операций сортировки Шелла
Размерность массивов |
Среднее количество операций |
1 |
1,000 |
2 |
2,476 |
3 |
5,451 |
4 |
11,345 |
5 |
18,465 |
10 |
82,704 |
15 |
168,198 |
20 |
355,913 |
25 |
502,636 |
30 |
699,109 |
50 |
2053,515 |
75 |
5462,953 |
100 |
8280,737 |
250 |
50102,515 |
500 |
200682,246 |
Далее необходимо построить график зависимости количества операций от длины массивов. График представлен на рисунке 2.2.2.
Рисунок 2.2.2 - График зависимости количества операций от длины массивов
Таблица 4 представляет собой таблицу со значениями длины массивов и среднего времени выполнения сортировки (среднего времени выполнения всех сравнений и перестановок).
Таблица 4 - Значения среднего времени выполнения операций сортировки Шелла
Размерность массивов |
Затраченное время (с) |
1 |
0,000000 |
2 |
0,000000 |
3 |
0,000000 |
4 |
0,000000 |
5 |
0,000000 |
10 |
0,000001 |
15 |
0,000001 |
20 |
0,000003 |
25 |
0,000004 |
30 |
0,000005 |
50 |
0,000013 |
75 |
0,000034 |
100 |
0,000050 |
250 |
0,000259 |
500 |
0,000892 |
Далее необходимо построить график зависимости затраченного на выполнение сортировки времени от длины массива. График представлен на рисунке 2.2.3.
Рисунок 2.2.3 - График зависимости затраченного времени от длины массивов
На основе полученных графиков, построим графики зависимостей y=n, y=n*log(n), y=n^2, y=n^3. Графики представлены на рисунке 2.2.4.
Рисунок 2.2.4 – Графики зависимости для сортировки Шелла
Проанализировав полученные результаты, можно сделать вывод о том, что график количества операций лежит между графиками y=n*log(n) и y=n^2. А следовательно, лучшее время для сортировки Шелла O(n*log(n)), а худшее - О(n^2).