Повторюсь: кто может написать что-то, обращайтесь.
QuickSort, продолжение
В прошлый раз я привёл код, в котором за "базовый"(интересно,
можно ли его так называть) брался центральный элемент(m:=a[(L+R) div 2];).
Существуют и другие варианты выбора базового элемента. Рассмотрим, почему
это так важно на примере:
Дан массив из пяти элементов 2
5 1 3 4. Будем действовать по нашему алгоритму:
- за базовый элемент мы выберем 1
- просматривая массив справа налево, найдем число меньшее либо равное
1, это
она и есть :)
- просматривая массив слева направо найдём число большее либо равное 1,
это число 2
- обменяем их
- получим массив 1 5
2 3 4
- процедура запустится рекурсивно для части массива 5
2 3 4, она преобразуется в 2
5 3 4
- процедура запустится рекурсивно для части массива 5
3 4, она преобразуется в 3
5 4
- процедура запустится рекурсивно для части массива 5
4 , она преобразуется в 4
5
Не такого поведения мы ждали от быстрой сортировки. Всё
пошло наперекосяк с самого начала,
когда за базовый элемент мы выбрали наименьшее число массива. В таких
случаях быстрая сортировка теряет свои достоинства и становится сортировкой
класса O(n2).
За базовый можно взять любой элемент. В некоторых алгоритмах за базовый
берётся первый элемент, наверное, это худший вариант(представьте, как
будет сортироваться отсортированный(масло масляное) массив). Брать средний
элемент, пожалуй, самый "демократичный" вариант. Если же у Вас
паническая боязнь, что кто-то специално подсунет данные с наименьшим средним
элементом, то Вы можете сгенерировать случайное число. Но это всё были
полумеры: получить плюху на случайно сгенерированных массивах они готовы
одинаково неплохо.
Самый лучший вариант - это взять средний из трёх элементов массива (поиск
медианы трёх). Целесообразно для сравнения брать левый, средний и правый
элементы массива. Поясню примером:
Дан массив 54
72 45 39 19 29 31 96 44 21 70 46 51 76 15 34,
выберем в нём базовый элемент. Найдём среднее из чисел 54
96 34. Это 54.
Реализуйте сами (попутно расставьте эти три числа в нужном порядке и "объясните"
алгоритму, что они уже на месте).
Вероятность худшего случая мы снизили до приемлемых размеров. Но у быстрой
сортировки есть ещё узкие места. Одно из них - это неадекватные реакции
на большое количество одинаковых элементов. Выход есть и из этой ситуации
- сменить алгоритм сортировки.
Оптимизация
1. Будем избавляться от рекурсии. Лишние 28 байт на
стеке нам не нужны. Стек, мы реализуем программно. Для начала взгляните
на процедуру(из прошлой статьи) сортировки и подумайте о том, что нужно
хранить в стеке.
Переменные i,j,m,t сохранять не надо(они отрабатывают своё до
рекурсивного вызова), остаются только L,R. Что из себя будет
представлять стек в программе? Обычный массив + индекс свободной ячейки.
2. Напоследок самое главное. По таблице замеров мы видим, что на маленьких
массивах быстрая сортировка заметно проигрывает. Т.к. алгоритм рекурсивный
и каждый новый вызов происходит для меньшего массива, следовательно, при
сортировке любого массива настанет момент, когда быстрая сортировка не
выгодна. Этот момент не фиксирован, попробовав разные значения, у меня
получилось, что на массивах длины <=20 нужно применять другой алгоритм.
Глядя на таблицу мы видим что на таких данных эффективнее всего InsertionSort.
3. Собрав все три оптимизации воедино, я получил такой код.
P.S. Целесообразность оптимизации смотрите в таблице.
Задачи
1. Найти количество различных чисел
среди элементов данного массива. 2. Имеется отсортированный по не убыванию массив из 65536
элементов. В нём случайным образом выбираются два элемента и меняются
местами. Эта операция повторяется 256 раз. Ваша задача упорядочить массив
по не убыванию. 3. На сельской улице живут Ивановы и Петровы. Необходимо,
используя минимальное число обменов, расселить их так, чтобы Ивановы жили
с одного конца улицы, а Петровы - с другого.
4. Имеется N камней веса А1,А2,...,АN. Необходимо разбить
их на две кучи таким образом,чтобы веса куч отличались не более чем в
2 раза. Если этого сделать нельзя, то указать это. 5. Имеются числа А1,А2,...,АN
и B1,B2,...,BN. Составить из них N пар
(Аi, Bj) таким образом, чтобы сумма произведений
пар была максимальна.
6. Задается словарь. Найти в нём все анаграммы (слова,
составленные из одних и тех же букв).
Присылайте решения, желательно с описанием, и они будут публиковаться.
