Методы сортировки
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
?м заданного ключа.
Таблица 4. Зависимость времени сортировки от кол-ва элементов в данном массиве
Кол-во элементовБыстрая сортировка, M = 1Быстрая сортировка, M = 256Поразрядная сортировка646549112824111351256160291605512375226416310241452247592204846955217832409613641036525788192276524611800171638442073880733625327688647673824388286553615841135129659086
График 4. Зависимость времени сортировки от кол-ва элементов в данном массиве
Таблица 5. Зависимость времени сортировки от степени перемешенности элементов массива
Степень перемешенности0255075100Быстрая сортировка, M = 129293054233838283307Быстрая сортировка, M = 25624812651245424813013Поразрядная сортировка12279531155324116451012095171195499
Таблица 6. Соотношение времени выполнения сортировок
ВремяБыстрая, M = 1Быстрая, M = 256ПоразряднаяБыстрая, M = 1309111,1817741590,002596429Быстрая, M = 25626160,84618536710,00219706Поразрядная сортировка1190561385,1444234455,15372711
График 5. Зависимость времени сортировки от степени перемешенности элементов массива
Вывод
В процессе выполнения работы, были выявлены особенности исследуемых алгоритмов сортировки данных.
1)Быстрая сортировка, M = 1:
Просто и адекватно запоминающийся алгоритм сортировки, один из самых распространенных. В данной работе он оправдал себя. По итоговым графикам видно, что время выполнения не сильно зависит от степени перемешенности элементов массива. На Графике 1 можно видеть сильный разброс времени выполнения сортировки. Такие погрешности, скорей всего можно отнести к технической реализации алгоритма. И убрать эту погрешность, оптимизировав и упростив алгоритм сортировки.
2)Быстрая сортировка, M = 256:
Поскольку алгоритм используется тот же, что и при первом типе сортировки есть небольшой разброс, который на больших массивах сводится к минимуму. Рассматривая графики График 1 и График 4 можно заметить, что по сравнению при параметре M = 1 график выглядит естественнее. К тому же по итогам Таблицы 5 видно, что скорость выполнения сортировки при параметре M = 256 немного быстрее аналога. Кроме того скорость выполнения стала менее зависимой от степени перемешенности.
3)Поразрядная сортировка:
Алгоритм достаточно запутанный, но после понимания реализуется не сложно и довольно таки быстро. Однако скорость его выполнения не радует. По данным Таблицы 5 видно, что данный алгоритм проигрывает методу быстрой сортировки почти в 400 раз, а это достаточно крупное число. Но плюс данного метода в том, что его можно применить для сортировки строк в алфавитном порядке. По Графику 3 можно заметить, что алгоритм слабо чувствителен к степени перемешенности элементов в массиве. Однако скорость сортировки очень резко падает при увеличении кол-ва элементов в массиве.
Подводя окончательные итоги, хочу сказать, что одним из самых лучших методов из трех данных проявил метод быстрой сортировки при параметре M = 256. Он прост в написании, быстр, по сравнению со своим аналогом при M = 1 и намного быстрее метода поразрядной сортировки. Метод поразрядной сортировки тоже хорош, но только не для сортировки чисел, а например, для сортировки строковых данных.