| Фермерская сортировка | Быстрая сортировка | ||
| 100 | 2 305 | 805 | 141 |
| 1 000 | 248 061 | 80 887 | 2 417 |
| 10 000 | 24 903 994 | 6 154 077 | 31 011 |
А что с количеством перестановок (табл. 2)? Здесь «фермерская» сортировка всё же в 3—4 раза обгоняет «пузырёк». Так что фермеру Лефту в сметливости не откажешь. И всё же этому «спортсмену» далеко до изобретения Райта! В сравнении с «пузырьком» выигрыш стократный, и стремительно растёт с ростом размера массива. Слава, слава фермеру Райту! Кстати, историки выяснили его настоящее имя: это англичанин Чарльз Хоар.
Итак, с чемпионом все ясно (рис. 96), но в чем секрет его успеха? Сравним чемпиона с отставшими. Чем больше массив, тем дольше он сортируется, – это справедливо для любого алгоритма. Долгие методы обрабатывают весь массив N раз, где N – размер массива. Поэтому их трудоемкость пропорциональна произведению N•N. По этой формуле вычисляют площадь квадрата, и такую зависимость называют квадратичной.
Иное дело – чемпион. Дробя массив на мелкие участки, быстрый алгоритм уменьшает число прохождений всего массива до величины Log2N. Поэтому его трудоемкость растёт пропорционально произведению N•Log2N. Опять логарифм? Да, мы помним его по двоичному поиску. Поскольку логарифм числа растёт очень медленно, это объясняет чемпионство QuickSort (рис. 97).
• Двоичный поиск – это самый быстрый способ поиска, но он требует предварительной сортировки массива.
• Простые методы сортировки – BubbleSort и FarmSort – работают очень медленно, съедая всю экономию от двоичного поиска.
• QuickSort – это быстрый способ сортировки, который в сочетании с резвым двоичным поиском ускорит работу ваших программ.
А) Исследуйте процедуру быстрой сортировки в пошаговом режиме (задайте небольшой размер сортируемого массива). Обратите внимание на изменение границ сортируемой части.
Б) Определите количество повторных входов в процедуру QuickSort и выходов из нее. Объявите глобальную переменную, назовем её Level – «уровень». В главной программе, перед вызовом процедуры QuickSort, эту переменную надо обнулить, а внутри процедуры добавить следующие операторы.
В начале процедуры QuickSort:
begin
Inc(Level); Writeln('Уровень на входе = ', Level);
