Главная >> Каталог задач >> Сортировка >>

Сравнение алгоритмов быстрой сортировки

• Случайные массивы
• Частично-отсортированные массивы
• Выводы
• Все реализации

По аналогии со сравнением сортировок, протестируем теперь по производительности и количеству перестановок различные варианты Быстрой сортировки:

1. Опорный элемент - середина (QSortCenter)
2. Опорный элемент - первый левый (QSortLeft)
3. Опорный элемент - левый, пропуск равных элементов (QSort3)
4. Опорный элемент - левый, пропуск равных, введение cutoff (QSort4)

Оценивать будем время выполнения, и количество перестановок элементов.

На вход каждой сортировки будем подавать целочисленные массивы с количеством элементов: 4000 - 20000.
В 2-х режимах:

• Массивы со случайно-сгенерированными числами
• Частично упорядоченные массивы

Время будем рассчитывать с точностью до микросекунд. На графиках время отображается в долях секунды.

В результате получим:

• Случайные массивы [скорость, перестановки]
• Частично-отсортированные массивы [скорость, перестановки]
• Выводы

 

Случайные массивы

 

Частично-отсортированные массивы

 

Выводы

1. Версия QSortLeft наихудшая по всем параметрам и во всех случаях
2. Самая быстрая версия - это QSortCenter (видно также сыграли немалую роль использование бинарной операции >> для получения середины и передача сдвинутого указателя на массив в каждой рекурсии вместо передачи указателя на весь массив)
3. При случайных массивах QSort4 делает меньше всего перестановок
4. При частичной отсортированности QSort3 делает меньше всего перестановок, а QSort4 - наоборот, больше всего

 

 

Реализации:

C++(7)   +добавить

1) Анализ быстрых сортировок массива на C++, code #51[автор:this]
2) QuickSortLeft.h на C++, code #52[автор:this]
3) QuickSortLeft.cpp на C++, code #53[автор:this]
4) QuickSort3.h на C++, code #54[автор:this]
5) QuickSort3.cpp на C++, code #55[автор:this]
6) QuickSort4.h на C++, code #56[автор:this]
7) QuickSort4.cpp на C++, code #57[автор:this]