Быстрая сортировка: алгоритм для работы с массивами данных

Что это? Быстрая сортировка – это алгоритм, изобретенный Тони Хоаром и использующийся для работы с большими массивами данных. Необходим для автоматизации процессов, ускорения работы программ, анализа и вывода информации.

Как работает? Классический алгоритм быстрой сортировки использует улучшенный пузырьковый метод. Из массива выбирается опорный элемент, с ним сравниваются остальные элементы и помещаются справа или слева, в зависимости от значения функция повторяется.

Суть быстрой сортировки Хоара

Данный алгоритм разработал в 1960 году Тони Хоар, которому требовалось отсортировать информацию на магнитной пленке, избегая многократной перемотки.

В качестве основы использовалась быстрая сортировка пузырьком, реализованная следующим образом.

• При каждом действии указывался опорный элемент быстрой сортировки, входящий в массив.
• Прочие значения из массива сопоставлялись с опорным. Меньшие помещались слева от него, а большие или равные – справа.
• Внутри полученных групп указывался новый опорный элемент, по которому повторно выполнялась сортировка. Операция повторялась, пока не оставалось только одно значение.

Подобно другим алгоритмам, метод быстрой сортировки данных придуман на основе бытового опыта. Если у вас есть множество карточек с заголовками на определенную букву, удобно разделить их на две группы, например, до буквы «Р» и после нее. Карточки с заголовками на букву «А», «Б», «Г» и далее до «Р» идут в одну группу, а на «Р», а также «С», «Т», «У» и до конца алфавита – в другую. Полученные группы снова делятся на две и так далее.

Узнай, какие ИТ - профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес

Павел Симонов

Исполнительный директор Geekbrains

Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов

Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

Получить подборку бесплатно

pdf 3,7mb

doc 1,7mb

Уже скачали 31751

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

В этой связи быстрая сортировка рекурсиями большого массива данных может потребовать очень много памяти. Этот недостаток позволяют исправить усовершенствованные методы быстрой сортировки.

Хотя быстрая сортировка и вызывает сложности с использованием памяти, этот алгоритм имеет ряд преимуществ:

• Самый быстрый алгоритм сортировки, если нет исходных данных о массиве, с которым нужно выполнить какие-то операции.
• Быстрая сортировка очень удобна для реализации программными средствами, независимо от выбранного языка программирования.
• Операция легко разделяется на несколько отдельных процессов.
• Быстрая сортировка – оптимальный алгоритм для операций над массивом с последовательным доступом, в котором нет возможности перейти в начало в произвольный момент.

Для данного метода важен корректный выбор опорного элемента. Он производится несколькими способами.

• Первое значение. Опорным элементом становится первое значение, указанное в массиве. Именно этот способ использовался Хоаром.
• Среднее значение. Элемент, находящийся в середине массива.
• Медианное значение. Используется элемент, располагающийся посередине массива в целом.

Читайте также!

Нюансы использования React js

Подробнее

Данный перечень не исчерпывающий. Другие методы используются, когда программисту заранее известно, упорядочен ли массив или все данные в нем следуют в произвольном порядке.

Вычислительная сложность алгоритма быстрой сортировки

Проанализировать эффективность быстрой сортировки достаточно сложно. Для лучшего понимания охарактеризуем ее вычислительную сложность, рассчитав количество сравнений при некоторых исходных величинах. Пусть, n – это степень двойки, n=2^k (k = log₂n). Опорное значение находится строго посередине списка, разделяя его на две группы одинакового размера.

Во время первичного прохода выполняется n-1 сопоставлений. В итоге формируются две группы, имеющие величину n/2. Далее сканирование каждой подгруппы требует n/2 сравнений. Суммарное количество сопоставлений на данном этапе равняется 2(n/2) = n.

На следующем шаге анализируются уже четыре группы данных, и нужно 4(n/4) сопоставлений, и т.д. Операция завершается после прохождения k сканирований, и сформированные группы содержат только один элемент. Суммарное количество сопоставлений примерно равняется:

• N + 2(n/2) + 4(n/4) + … + n(n/n) = n + n + … + n = n * k = n * log₂n

Для стандартного массива вычислительную сложность быстрой сортировки можно оценить по формуле O(n log₂ n). Быстрая сортировка в изложенном примере имеет соответствующий вид, если данные в массиве рассортированы по возрастанию. Ключевое значение в этом случае оказывается ровно посередине списка.

При сортировке по убыванию во время первичного сканирования опорное значение находится посередине списка и в обеих сформированных подгруппах меняется местами с остальными значениями. Получившаяся группа элементов практически отсортирована, формула выглядит следующим образом: O(n log₂n).

Наиболее сложным случаем для функции быстрой сортировки будет повторяющееся размещение опорного значения в одноэлементной группе, когда все остальные значения будут оказываться во второй группе. Такая ситуация возникает, если опорным элементом постоянно оказывается наименьшее значение. Для примера разберем ряд чисел. 3, 8, 1, 5, 9.

При первичном сканировании выполняется n сопоставлений, в большем подсписке находится n-1 элементов. При втором сканировании в данном подсписке будет n-1 сопоставлений, сформируется группа из n-2 элементов и т.д. Суммарное количество сопоставлений при использовании быстрого алгоритма сортировки массива составит:

• n + n-1 + n-2 + … + 2 = n(n+1)/2 — 1

Формула QuickSort наиболее часто используется в приложениях для сортировки данных. Если для вас неприемлема производительность наиболее тяжелого варианта быстрых методов сортировки массивов, то можно попробовать пирамидальную сортировку. Ее сложность выражается формулой O(n log₂n) и определяется лишь размером массива.

Время выполнения алгоритма быстрой сортировки

Длительность операции быстрой сортировки определяется выбором ключевого значения (pivot), или, иначе говоря, сбалансированностью. При сбалансированной группировке обработка данных занимает не больше времени, чем сортировка слиянием. В ином случае процедура выполняется не быстрее, чем при сортировке вставкой.

Наихудшая группировка

Наихудшая группировка наблюдается в случае, когда по завершении операции формируются две подгруппы, в одной из которых оказывается 0 значений, а в другой – n-1 элементов.

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

T(n) = Thetta(n) + T(0) + T(n-1) = Thetta(n) + T(n-1)

Каждое значение массива в ходе сортировки сопоставляется с ключевым элементом n раз, поэтому длительность разбивки массива на группы выражается формулой Thetta(n). Длительность операции quicksort(p,0) составляет 0, поскольку она моментально завершается. Применяя значение T(n — 1) = Θ(n-1) + T(n — 2), получаем формулу:

T(n) = Thetta(n) + Thetta(n — 1) + Thetta(n — 2) + … = Thetta(n^2).

Наихудшая группировка наблюдается в случае, если список изначально отсортирован по убыванию, а на выходе должен получиться список по возрастанию. На эффективную быструю сортировку рассчитывать не приходится, поскольку ключевое значение оказывается минимальным, в ходе группировки появляется q = 1. В результате сформируется два списка, в одном из которых 0 значений, а во втором – n-1.

Дарим скидку от 60%
на курсы от GeekBrains до 10 ноября

Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей

Забронировать скидку

Наилучшая группировка

При идеальных условиях операция быстрой сортировки разделяет задачу на две подзадачи. Их размер не более n/2. В этом случае выполняется самая быстрая сортировка массива, длительность процедуры рассчитывается рекуррентной формулой:

T(n) <= 2T(n/2) + Thetta(n)

T(n) = O(n lgn)

Сбалансированная группировка

Группировка завершится за время О(nlgn), даже если выполняется разбивка в соотношении 99:1. Она может выглядеть несбалансированной, но в асимптотическом пределе работа алгоритма происходит аналогично делению задачи на две равнозначные подзадачи.

Быстрая сортировка вставками и другие методы сортировки

Группировка вставками напоминает тасование колоды карт с именами. Каждое из них указывается в карточке, после чего они сортируются в алфавитном порядке путем вставки в верхнюю половину стопки в соответствующее место. Для примера проанализируем последовательность A = 50, 20, 40, 75, 35.

В функцию InsertionSort направляется массив A и длина массива n. Проанализируем i-ое сканирование (1<i<n-1).

Подгруппа от A[0] до A[i-1] уже сформирована по возрастанию. Значение A[i] укажем как вставляемое (TARGET), перемещая его к началу массива и сопоставляя со значениями A[i-1], A[i-2] и т.д. Анализ останавливается на значении A[j], равном (TARGET) или меньше его, либо расположенном в начале массива (j = 0). По ходу перемещения к началу массива все значения перемещаются правее (A[j] = A[j-1]). При обнаружении ячейки, соответствующей значению A[i], последнее помещается в точку j.

Только до 14.11

Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней

Список документов:

ТОП-100 площадок для поиска работы от GeekBrains

20 профессий 2023 года, с доходом от 150 000 рублей

Чек-лист «Как успешно пройти собеседование»

Чтобы получить файл, укажите e-mail:

Введите e-mail, чтобы получить доступ к документам

Подтвердите, что вы не робот,
указав номер телефона:

Введите телефон, чтобы получить доступ к документам

Скачать подборку бесплатно pdf 2,5mb

Уже скачали 52300

Я подтверждаю согласие на обработку персональных данных.

Для группировки списками необходимо выполнить фиксированное количество сканирований. На n-1 этапе размещаются значения от A[1] до A[n-1]. На i-ом сканировании вставка выполняется в подгруппу A[0]–A[i], и ей нужно около i/2 сопоставлений. Суммарное количество сопоставлений равняется:

• 1/2 + 2/2 + 3/2 + … + (n-2)/2 + (n-1)/2 = n(n-1)/4.

По сравнению с иными алгоритмами, в группировке вставками не выполняются обмены. Сложность определяется количеством сопоставлений и равняется O(n²). Оптимальная ситуация – когда первоначальный массив отсортирован. В этом случае на i-ом сканировании вставка осуществляется в ячейку A[i]. Суммарное число сопоставлений равняется n-1. Следовательно, сложность выражается, как O(n). Худшая ситуация наблюдается тогда, когда массив сгруппирован в порядке убывания. Каждая вставка выполняется в ячейку A[0], и для нее нужно выполнить i сопоставлений. Суммарное число сопоставлений равняется n(n-1)/2, т.е. сложность составляет O(n²).

Читайте также!

Что такое API: технология, виды, примеры

Подробнее

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

Также описываемый способ лучше подойдет для сравнительно стабильного массива, в который периодически добавляются один-два элемента.

Мы описали способы группировки массива со сложностью O(n²), разобрали, как работает быстрая сортировка. Методы на основе деревьев показывают лучшую скорость работы – O(n log₂n). Для их работы необходимо выполнять копирование списка в дерево и обратно, однако в итоге производительность выше благодаря лучшей эффективности самой группировки.

Популярные статьи

Высокооплачиваемые профессии сегодня и в ближайшем будущем

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

Востребованные удаленные профессии: зарабатывайте, не выходя из дома

Разработчик игр: чем занимается, сколько зарабатывает и где учится

Как выбрать профессию по душе: детальное руководство + ценные советы

Часто встречающийся алгоритм пирамидальной группировки тоже сортирует массив «на месте» и показывает производительность O(n log₂n). Тем не менее, разработанная Хоаром быстрая сортировка чаще всего оказывается производительнее пирамидальных алгоритмов, поэтому ее широко используют в программном коде.

Автор статьи:

Редакция сайта GeekBrains Шеф-редактор раздела Программирование