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

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

#Часики на js. (83838 hits)
#Сравнение алгоритмов сортировки массива. (166518 hits)
#Синус. (54184 hits)
#Передача данных из основного во всплывающее-popup окно через POST. (109981 hits)
#Рисование полусферы. (22840 hits)
#Преобразование целых чисел в битовый массив. (31972 hits)
#Поразрядная сортировка, общий принцип. (119639 hits)
#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (26485 hits)
#Динамическая очистка выпадающего списка (select) на javascript. (82021 hits)
#Таймер. (35568 hits)
#Сортировка Шелла, обший принцип. (136354 hits)
#Подключение. (20937 hits)
#Рисование линии. (33098 hits)
#Код. (168078 hits)
#Замена символа строки. (435553 hits)
#Вычисление медианы заданной выборки. (43985 hits)
#Заливка замкнутой области. (56378 hits)
#Сравнение алгоритмов быстрой сортировки. (66428 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (33069 hits)
#Рисование прямоугольника. (26060 hits)


Главная >> Каталог задач >> Сортировка >> Сравнение алгоритмов быстрой сортировки

<< назад
распечататьобсудить >>


Сравнение алгоритмов быстрой сортировки
реализации: C++, количество: 7

Aвтор: this
Дата: 16.04.2003
Просмотров: 66427
Рейтинг: 3/7,4.87(3880)
реализации(исходники) +добавить

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

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

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

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

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

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

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

 

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



 

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



 

Выводы

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

 

 



Реализации: C++(7)   +добавить реализацию

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


<< назад наверх
распечататьобсудить >>

каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.017691 секунд
Количество запросов к БД: 14, gzip: off