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

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

#Как посчитать одинаковые пары за 1 проход (самая быстрая версия!). (2149 hits)
#Сортировка выбором, общий подход. (72844 hits)
#Подсветка синтаксиса. (31461 hits)
#Постраничный вывод. (72722 hits)
#Плоттеры для рисования графиков. (29680 hits)
#Сортировка Шелла, оптимальный выбор приращений. (195081 hits)
#Рисование прямоугольника. (31299 hits)
#Наибольший общий делитель. (192500 hits)
#Циклический сдвиг массива или строки - 3 уникальных алгоритма. (389215 hits)
#Улучшение быстрой сортировки. (76903 hits)
#Вычисление минимального / максимального значения. (74389 hits)
#Просмотр изображения во всплывающем окне. (89251 hits)
#Валидация, динамическая проверка заполнения html форм. (209201 hits)
#Полезные утилиты, небольшие api и библиотеки и проч.. (69732 hits)
#Преобразование сумм из цифрового представления в строковое. (175671 hits)
#Шифрование произвольных данных. (328764 hits)
#Глубокое полное клонирование. (35802 hits)
#Бинарный поиск в массиве и его разновидности. (169246 hits)
#Поиск дубликатов внутри файла. (31345 hits)
#Относительный путь к файлу. (39741 hits)


Главная >> Каталог задач >> Сортировка >> Быстрая Сортировка (quick sort) >> Улучшение быстрой сортировки

Улучшение быстрой сортировки

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

Коротко:

Быстрая сортировка(функция qsort1) достаточно хорошо справляется с массивом случайных чисел, но если на вход подается уже частично упорядоченная последовательность либо последовательность содержащая подпоследовательности из одинаковых элементов, расположенных рядом - время выполнения алгоритма значительно возрастает, стремясь к ~ O(n2). В тоже время такой алгоритм как сортировка вставкой - с такими случаями справляется "на ура", сортируя со скоростью ~ O(n). Поэтому используем здесь следующий подход: если в сортируемой последовательности в алгоритме быстрой сортировке остается меньше cutoff элементов - они сортируется сортировкой вставками. cutoff - некоторая константа(которая зависит от начальных условий и обычно равна 3-40).

Подробно:

По книге Джона Бентли:
"Жемчужины программирования"

"...Функция qsort1 быстро сортирует массив случайных чисел, но что, если на вход будет подана уже упорядоченная последовательность? Программисты часто используют сортировку для того, чтобы одинаковые элементы оказались рядом. Следовательно, нужно рассмотреть крайний случай: массив из n одинаковых элементов. Сортировка вставкой работает на таких данных очень быстро: каждый элемент сдвигается на 0 позиций, поэтому время выполнения растет как О(n). Функция qsort1 справляется с такими данными очень плохо. Каждое из n-1 разбиений требует время О(n) для выделения одного элемента, поэтому полное время выполнения растет как О(n2). Время обработки для n = 1 000 000 возрастает с одной секунды до двух часов.

Можно обойти эту проблему, используя двусторонний алгоритм разбиения с приведенным на рис. 11.7 инвариантом:

Индексы i и j инициализируются граничными индексами разбиваемого массива. Главный цикл содержит два вложенных цикла. Первый вложенный цикл сдвигает i вверх, пропуская меньшие элементы, а второй увеличивает j, пропуская большие элементы и останавливаясь на меньшем. Главный цикл проверяет, не пересекаются ли эти индексы, и переставляет соответствующие элементы.

Но как такой код будет работать в ситуации, когда все элементы равны? Первая мысль: пропустить эти элементы, чтобы не делать лишней работы, но в результате получается квадратичный для массива из одинаковых элементов алгоритм. Поэтому каждое сканирование будет останавливаться на одинаковых элементах, которые затем будут обмениваться. Хотя в этом варианте обменов будет производиться больше, чем требуется, такая программа будет превращать худший случай с массивом из одинаковых элементов в лучший, требующий почти в точности n*log2n и сравнений. Псевдокод, реализующий описанный алгоритм разбиения, примет вид:

 псевдокод: Быстрая сортировка, оптимизация №1 (qsort3)  ссылка
  1. void qsort3(l, u)
  2. if l >= u
  3. return
  4.  
  5. t = x[l]
  6. i = l
  7. j = u+1
  8. while (1)
  9. /* пропуск элементов справа и слева,
  10. чтобы не делать лишней работы */
  11. do i++ while i <= u && x[i] < t
  12. do j-- while x[j] > t
  13.  
  14. if i > j
  15. break;
  16. swap(i, j)
  17.  
  18. swap(l, j)
  19.  
  20. qsort3(l, j-1)
  21. qsort3(j+1, u)


Избавляясь от квадратичного поведения в худшем случае, этот код и в среднем делает меньше обменов, чем qsort1.

Рассмотренные нами программы быстрой сортировки разбивали массив относительно первого встреченного элемента. Это хорошо подходит для случайных входных данных, но может сильно замедлить работу для некоторых упорядоченных последовательностей. Если массив уже отсортирован по возрастанию, его придется разбивать относительно первого элемента, затем относительно второго и так далее, что потребует времени О(n2). Мы можем избежать этого, выбирая элемент для разбиения случайным образом — обменивая местами элемент х[l] со случайным элементом из диапазона x[l..u]:

swap(l, randint(l, u))

Если у вас нет функции randint, обратитесь к задаче, которая посвящена написанию собственного генератора случайных чисел(прим. ред.:на данном сайте этому посвящана задача собственный генератор случайных чисел). Каким бы кодом вы ни пользовались, внимательно проследите за тем, чтобы функция randint возвращала значение из диапазона [l, u] — выход за его границы приведет к ошибкам. Объединив случайный выбор центрального элемента с двусторонним разбиением, мы получим программу быстрой сортировки, работающую за время O(n*log n) для любого входного массива. Усреднение делается вызовом генератора случайных чисел, а не анализом возможного распределения входных данных.

Наша программа быстрой сортировки большую часть времени тратит на сортировку очень маленьких подмножеств. Такие массивы было бы проще всего сортировать каким-либо несложным методом вроде сортировки вставкой, а не тратить на них всю мощь быстрой сортировки. Боб Седжвик разработал весьма хитроумную реализацию этой идеи. Когда функция быстрой сортировки вызывается для небольшого массива (то есть l и u близки), она не делает ничего. Реализуется это путем замены первого оператора if нашей функции на следующий код:

if u-l > cutoff return

Здесь cutoff — некоторое небольшое целое число. После завершения работы функции массив будет не отсортирован до конца, но разбит на небольшие группы случайно упорядоченных элементов, причем все элементы одной группы будут меньше любого элемента всех групп, расположенных справа от данной. Сортировать элементы внутри групп нужно каким-то другим методом, и тут лучше всего подходит сортировка вставкой, поскольку массив уже почти упорядочен.

Для решения задачи сортировки целиком придется выполнить два вызова:

qsort4(0, n-1)
isort3()

На последнем этапе оптимизации программы можно раскрыть вызов функции swap во внутреннем цикле (поскольку другие два вызова swap лежат вне внутреннего цикла, их раскрытие не даст ощутимого результата). Последняя версия программы Quicksort примет вид:

 псевдокод: Быстрая сортировка, оптимизация №2 (qsort4)  ссылка
  1. void qsort4(l, u)
  2. if u - l < cutoff
  3. return
  4.  
  5. swap(l, randint(l, u))
  6. t = x[l]
  7. i = l
  8. j = u+1
  9. while (1)
  10. /* пропуск элементов справа и слева,
  11. чтобы не делать лишней работы */
  12. do i++ while i <= u && x[i] < t
  13. do j-- while x[j] > t
  14.  
  15. if i > j
  16. break;
  17. tmp = x[i] x[i] = x[j] x[j] = tmp
  18.  
  19. swap(l, j)
  20.  
  21. qsort4(l, j-1)
  22. qsort4(j+1, u)
  23.  
  24. /* При этом вызов всей процедуры сортировки
  25. в программе будет иметь вид: */
  26. qsort4(0, n-1);
  27. isort3();


В табл. 11.2 приведены сводные данные по всем версиям быстрой сортировки. Правая колонка указывает среднее время работы в наносекундах, требуемое для сортировки массива из n случайных целых чисел. Многие алгоритмы могут вести себя как квадратичные для некоторых конкретных входных данных.

Функция qsort состоит из 15 строк быстрой сортировки и 5 строк сортировки вставкой. Для миллиона случайных чисел время выполнения лежит в диапазоне от 0,6 с для библиотечной функции sort языка C++ до 2,7 с для библиотечной функции qsort языка С.
..."

Джон Бентли

Реализации:

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

1) Быстрая сортировка QSort3 (оптимизация №1) на C++, code #15[автор:this]
2) Быстрая сортировка QSort4 (оптимизация №2) на C++, code #16[автор:this]