Главная
>>
Каталог задач
>>
Сортировка
>>
Сравнение алгоритмов быстрой сортировки
Сравнение алгоритмов быстрой сортировки
Aвтор:
this
Дата:
16.04.2003
Просмотров: 74069
реализации(C++: 7шт...)
+добавить
- Случайные массивы
- Частично-отсортированные массивы
- Выводы
- Все реализации
По аналогии со сравнением сортировок, протестируем теперь по производительности и количеству перестановок различные варианты Быстрой сортировки:
- Опорный элемент - середина (QSortCenter)
- Опорный элемент - первый левый (QSortLeft)
- Опорный элемент - левый, пропуск равных элементов (QSort3)
- Опорный элемент - левый, пропуск равных, введение cutoff (QSort4)
Оценивать будем время выполнения, и количество перестановок элементов.
На вход каждой сортировки будем подавать целочисленные массивы с количеством элементов: 4000 - 20000.
В 2-х режимах:
- Массивы со случайно-сгенерированными числами
- Частично упорядоченные массивы
Время будем рассчитывать с точностью до микросекунд. На графиках время отображается в долях секунды.
В результате получим:
Случайные массивы
Частично-отсортированные массивы
Выводы
- Версия QSortLeft наихудшая по всем параметрам и во всех случаях
- Самая быстрая версия - это QSortCenter (видно также сыграли немалую роль использование бинарной операции >> для получения середины и передача сдвинутого указателя на массив в каждой рекурсии вместо передачи указателя на весь массив)
- При случайных массивах QSort4 делает меньше всего перестановок
- При частичной отсортированности 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]