Задача 3 посвящена выбору оптимальной величины порога cutoff.
На последнем этапе оптимизации программы можно раскрыть вызов функции swap во внутреннем цикле (поскольку другие два вызова swap лежат вне внутреннего цикла, их раскрытие не даст ощутимого результата). Последняя версия программы Quicksort приведена в листинге 11.6.
Листинг 11.6. Быстрая сортировка: версия 4 (итоговая)
void qsort4(l. u) if u - 1 < cutoff ret urn swap(1, randint(1, u)) t = x[l ] . i=l.j = u + 1 1 oop
do i++ while i <- и && x[i] < t do j- - whi1e x[j] > t if i > J break
temp = x[ 1 ] ; x[i] = x[j]: x[j] = temp swapd . j) qsort4d . j-1) qsort4(j+l. u)
Задачи 4 и 11 посвящены дальнейшему улучшению производительности быстрой сортировки.
В табл. 11.2 приведены сводные данные по всем версиям быстрой сортировки. Правая колонка указывает среднее время работы в наносекундах, требуемое для сортировки массива из п случайных целых чисел. Многие алгоритмы могут вести себя как квадратичные для некоторых конкретных входных данных.
Таблица 11.2. Быстрая сортировка
Программа Объем кода (строк языка С) Время, не
Библиотечная функция языка С qsort 3 137л log2 п
Быстрая сортировка 1 9 60п log, п
Быстрая сортировка 2 9 56пlog2 п
Быстрая сортировка 3 14 44лlog2л
Быстрая сортировка 4 15+5 36иlog2 л
Библиотечная функция C++ sort 1 30л log2 п
Функция qsort состоит из 15 строк быстрой сортировки и 5 строк сортировки вставкой. Для миллиона случайных чисел время выполнения лежит в диапазоне от 0,6 с для библиотечной функции sort языка C++ до 2,7 с для библиотечной функции qsort языка С. В главе 14 мы изучим алгоритм, гарантированно сортирующий п целых чисел за O(nlogn) для любых входных данных (даже в худшем случае).
Опубликовал vovan666
April 17 2013 00:02:44 ·
0 Комментариев ·
3782 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
