CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Переворот символов строки (или элементов одномерного массива). (109855 hits)
#Динамическая очистка выпадающего списка (select) на javascript. (88011 hits)
#Заполнение 2-го выпадающего списка (select) в соответствии с выбором в первом. (44479 hits)
#Сортировка выбором, общий подход. (70476 hits)
#Вычисление двойного интеграла с использованием MPI. (58347 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (141330 hits)
#Замена символа строки. (440646 hits)
#Найти максимальную сумму в последовательности. (131084 hits)
#Шифрование произвольных данных. (325522 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (96723 hits)
#Бинарный поиск в массиве и его разновидности. (162819 hits)
#Постраничный вывод. (69721 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (37160 hits)
#Интерактивная, динамическая подгрузка картинок. (68124 hits)
#Заливка замкнутой области. (60754 hits)
#Сглаживание кривой В-сплайном. (36992 hits)
#Работа с камерой. (34326 hits)
#Простая геометрическая и текстовая анимация. (399375 hits)
#Простой генератор случайных чисел. (131827 hits)
#Рисование множества Мандельброта. (42482 hits)


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

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

Aвтор:
Дата:
Просмотров: 72089
реализации(C++: 7шт...) +добавить

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

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

  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]