Зададимся целью исследовать как же поведут себя в реальных задачах сортировки элементарных массивов такие алгоритмы, как: быстрая, пирамидальная, пузырьковая, выбором, вставками, Шелла, Шейкер-сортировка.
Оценивать будем время выполнения, и количество перестановок элементов.
На вход каждой сортировки будем подавать целочисленные массивы с разным количеством элементов: от 10 до 20000.
В 2-х режимах:
Помимо этого логично будет проводить 2 вида сравнения:
Время будем рассчитывать с точностью до микросекунды. При сравнении на малых размерностях в целях повышения точности время будет отображаться в долях миллисекунды, при больших же размерностях - в долях секунды.
Рассмотрим далее все эти комбинации, погнали!
Как видим по скорости лидирует быстрая сортировка. Самые медленные - это пузырьковая и Шейкера.
По количеству перестановок - меньше всего их делает как это ни странно сортировка выбором, затем конечно же быстрая сортировка. Больше всего перестановок делают опять же пузырьковая, Шейкера и Выбором.
Т.о. можно констатировать тот факт, что такие похожие по принципу сортировки алгоритмы как Выбором и Вставками, показывающие почти что одинаковую скорость, радикально отличаются по количеству перестановок: первая(выбором) - делает их меньше чем любой из представленных алгоритмов, вторая(вставками) - наоборот, больше всего.
По сравнению с полностью случайными массивами в случае частичной отсортированности на малых размерностях констатируем следующие факты:
Не видно Быструю, Пирамидальную и сортировку Шелла, поэтому:
По сравнению со случайными массивами на малых размерностях в случае больших размерностей констатируем следующие факты:
По сравнению с количеством перестановок на малых размерностях - значительных изменений не наблюдается.
Смотрим что происходит с Пирамидальной, Быстрой и Шелла:
По сравнению с частичной отсортированностью на малых размерностях делаем следующие выводы:
В отличие от перестановок на малых размерностях - здесь пирамидальная сортировка обходит Шелла, делая swap-ов значительно меньше. Лидирует как обычно - сортировка выбором.
Быстрая сортировка лидирует по производительности во всех тестах. По количеству перестановок она уступает лишь сортировке Выбором.
Сортировка выбором по производительности в общем случае мало отличается от Вставками, но вот по количеству перестановок - лидирует во всех тестах.
Пирамидальная сортировка и сортировка Шелла: на размерностях ~ больше 10000 пирамидальная быстрей во всех случаях. И лишь на меньших размерностях + в случае случайных значений - сортировка Шелла превосходит пирамидальную.
Шейкер и пузырьковая: первая конечно быстрей, но по количеству перестановок при частичной отсортированности - пузырьковая выигрывает, т.е. делает их меньше.