Алгоритм быстрой сортировки — это наиболее известный алгоритм сортировки информационных данных, изобретённый Т. Хоаром.
Введение
Алгоритм быстрой сортировки представляет собой усовершенствованный алгоритм, основанный на методике прямого обмена. Прямой обмен использовали алгоритмы пузырьковой и шейкерной сортировки, которые обладали невысокой производительностью. Главным и основным отличием быстрой сортировки является выполнение перестановок на самом большом, из возможных, расстоянии. Кроме того, по итогам выполнения каждого перебора выполняется разделение всех компонентов на две независящие друг от друга группы. По сути простая модернизация наименее производительного способа сортировки привела в итоге к одному из самых производительных сортировочных способов.
Алгоритм быстрой сортировки
Алгоритм быстрой сортировки выполняется следующим образом:
- Необходимо сделать выбор элемента, который будет использован как опорный. Им может стать каждый из набора элементов. Этот выбор не влияет на корректную работу алгоритма, но способен повлиять на его производительность.
- Выполнить сравнение всех оставшихся компонентов с опорным и перераспределить их в составе массива так, чтобы образовать три набора элементов (отрезка): больше опорного, равны опорному и меньше опорного.
- Для элементов групп «больше» и «меньше» требуется повторить рекурсивно ту же очерёдность действий, при условии, что их размер превышает единичный.
Но, как правило, массив подразделяют только на две составляющие. К примеру, «меньше опорного» и «больше и равны опорному». Это позволяет упростить алгоритм и сделать его более эффективным.
Т. Хоар изобрёл такую методику для машинного перевода текстов. В то время весь словарный запас сохранялся на магнитной ленте, и разработанный Т. Хоаром метод сортировки давал возможность выполнить перевод текста за один проход магнитной ленты. Отпадала необходимость перематывать ленту на начало. Идея этого алгоритма пришла в голову к Т. Хоару, когда он проживал в СССР и проходил там обучение по специализации «компьютерный перевод». Он разрабатывал англо-русский разговорный словарь.
Выбор опорного элемента
В начале использования алгоритма быстрой сортировки в качестве опорного служил первый элемент. Это могло существенно снижать эффективность сортировки. Лучшие результаты даёт выбор медианного, то есть среднего элемента, что является оптимальным вариантом. Но нахождение такого элемента требует значительных вычислительных ресурсов. Более простой способ определения опорного элемента предложил Ломуто, и он был описан в популярных изданиях. В качестве опорного берётся последний элемент, а в алгоритме сохраняется индекс в специальной переменной. В случае нахождения элемента, который меньше или равен опорному, выполняется увеличение индекса и данный элемент ставится впереди опорного. Данная методика разбиения менее громоздка, чем у Т. Хоара, но и не такая эффективная. Если массив уже прошёл сортировку или имеет равные по величине компоненты, то быстрая сортировка становится менее сложной. Есть разные методы, которые позволяют оптимизировать эту сортировку.
Разбиение Хоара
Эта методика применяет индекс в начале массива и ещё один в его конце. Индексы движутся во встречном направлении до тех пор, пока не обнаружатся два элемента, один из которых больше опорного и располагается перед ним, а второй меньше опорного и располагается за ним. Найденные элементы следует поменять местами, и такие обмены выполняются до момента пересечения индексов. Затем согласно алгоритму, возвращается последний индекс. Эта методика Т. Хоара имеет большую эффективность, чем схема Ломуто, поскольку среднее количество обменных операций примерно в три раза меньше, и она эффективнее даже при равенстве всех элементов. Но следует заметить, что данная методика сортировки нестабильна.
Сложность алгоритма
Обобщённая сложность алгоритма зависит только от числа делений, то есть от глубины рекурсивных операций. Глубина этих операций имеет зависимость от состава входных данных и методики определения опорного элемента. При самом благоприятном варианте при всех операциях деления, массив подразделяется на две практически одинаковые составляющие.
«Удачным» считается подразделение, если опорный элемент оказывается в числе центральных пятидесяти процентов элементов части массива, которая делится. Вероятность такого стечения обстоятельств в плане случайного расположения элементов равняется 0,5.
В случае удачного разделения объёмы выделяемых частей массива могут составлять не менее двадцати пяти процентов и не более семидесяти пяти от исходного объёма. Так как каждая выделенная часть массива тоже имеет случайное расположение, то эти положения можно применить к каждому периоду сортировки и каждому начальному компоненту массива. В самом худшем случае каждое деление выдаёт две части массива, размеры которых будут 1 и n – 1, что означает, что при каждой очередной рекурсии массив большего размера станет на единицу меньше, чем в прошлый раз. Это возможно, если опорным элементом на всех этапах окажется самый маленький элемент, или самый большой из всего набора элементов, подлежащих обработке.
При самом простом определении опорного элемента, когда выбирается или первый, или последний элемент в массиве, подобный эффект может дать массив, который уже отсортирован в прямом или в обратном направлении. Но число выполняемых обменных операций и взаимосвязанное с ними общее время работы не считается самым большим недостатком. Плохо в данном случае то, что глубина рекурсивных процедур при реализации алгоритма может достичь величины n, а это означает, что адрес возврата, а также локальные переменные, участвующие в процедуре подразделения массива, должны быть сохранены n раз. Если значение переменной n достаточно велико, то в худшем случае возможно переполнение памяти стека при выполнении программы алгоритма.
