- 6 августа 2025
- 5 минут
- 423
Алгоритм быстрой сортировки Хоара в Python
Статью подготовили специалисты образовательного сервиса Zaochnik.
Алгоритм быстрой сортировки, известный также как Quicksort, разработал английский ученый Чарльз Хоар в 1960 году.
Суть быстрой сортировки во многом аналогична методу сортировки слиянием. Выбирается элемент `q`, который называется барьерным, и массив делится на две части, при этом элементы переупорядочиваются. В одной части размещаются элементы, меньше или равные `q`, а в другой – большие или равные. Затем необходимо просто отсортировать обе части и объединить их без дополнительного слияния.
Быстрая сортировка Хоара
Алгоритм простой реализации
Простейшая версия быстрой сортировки Хоара на Python выглядит так:
```python
import random
def QuickSort(A):
if len(A) <= 1:
return A
else:
q = random.choice(A)
L = []
M = []
R = []
for elem in A:
if elem < q:
L.append(elem)
elif elem > q:
R.append(elem)
else:
M.append(elem)
return QuickSort(L) + M + QuickSort(R)
```
В этом примере массив `L` собирает элементы, меньшие `q`, массив `R` — большие `q`, а массив `M` — равные `q`. Трехуровневое разделение применяется для предотвращения зацикливания в случае, когда в массиве останутся лишь равнозначные элементы. Элемент `q` - барьерный элемент - извлекается из массива случайным образом с помощью записи `random.choice` (где `choice` - функция импортируемого модуля `random`).
Функциональный стиль
Тот же алгоритм на языке Python можно записать более лаконично в функциональном стиле:
```python
import random
def QuickSort(A):
if len(A) <= 1:
return A
else:
q = random.choice(A)
L = [elem for elem in A if elem < q]
M = [q] * A.count(q)
R = [elem for elem in A if elem > q]
return QuickSort(L) + M + QuickSort(R)
```
Тем не менее, такая реализация, как и метод сортировки слиянием, требует дополнительной памяти O(n).
Реализация без дополнительной памяти
Алгоритм быстрой сортировки также можно реализовать не используя дополнительную память:
```python
import random
def QuickSort(A, l, r):
if l >= r:
return
else:
q = random.choice(A[l:r + 1])
i = l
j = r
while i <= j:
while A[i] < q:
i += 1
while A[j] > q:
j -= 1
if i <= j:
A[i], A[j] = A[j], A[i]
i += 1
j -= 1
QuickSort(A, l, j)
QuickSort(A, i, r)
```
Данная реализация выполняет сортировку элементов списка `A` «на месте», точнее сказать модифицирует (перезаписывает) переданный список. Два параметра `l` и `r` указывают на индексы первого и последнего элементов фрагмента списка, который необходимо отсортировать. Чтобы произвести сортировку всех элементов списка необходимо вызвать функцию `QuickSort(A, 0, len(A) - 1)`.
При условии `l >= r`, сортировка не нужна, по той причине - либо срез является пустым, либо содержит один элемент. В противном случае выбирается случайный барьерный элемент. Два указателя `i` и `j` используются для перестановки элементов в таком виде, чтобы все элементы, значение которых меньше или равно `q`, оказались слева, а все элементы, значение которых больше или равно `q`, — справа. После распределения рекурсивно сортируются полученные части списка.
Эта версия не требует дополнительной памяти, кроме памяти для выполнения рекурсии.
Асимптотические характеристики алгоритма Хоара
Сложность алгоритма быстрой сортировки (сортировки Хоара) обусловлена методом выбора барьерного элемента. В благоприятном случае, на шаге каждого выбора элемент должен быть медианой. Однако, нахождение медианы — это сложная задача. К примеру, когда в качестве барьерного элемента выбрать первый или последний элемент, в случае уже отсортированного массива скорость выполнения будет — из-за того, что на каждой рекурсии отделяется только один элемент.
Поэтому в большинстве реализаций быстрых сортировок в качестве барьерного элемента выбор происходит на случайный элемент. Ситуация, когда всегда выбирается наименьший элемент, маловероятна, однако в таком случае алгоритм будет выполняться за O(n²).
В теории вероятностей показано, что при случайном выборе элемента и делении массива две части будут иметь в среднем одинаковый размер, и глубина рекурсии будет составлять O(log n). Средняя временная сложность алгоритма будет O(n log n).
Быстрая сортировка — это алгоритм, который относится к классу «разделяй и властвуй». Именно такие алгоритмы наиболее быстрые по сравнению с другими.
Программирование
14.06.2024
120
15