Быстрая сортировка

9.1 Определение быстрой сортировки

Быстрая сортировка (Quick Sort) — это эффективный алгоритм сортировки, который использует подход "разделяй и властвуй". Он работает путём выбора опорного элемента (pivot), разделения массива на два подмассива — элементы, меньшие опорного, и элементы, большие опорного, а затем рекурсивного применения того же процесса к каждому подмассиву.

Алгоритм быстрой сортировки появился как попытка решить проблему «как можно быстрее перебросить влево маленькие элементы, а вправо — большие». Допустим, у нас самый маленький элемент — крайний справа, можно ли как-то быстро перебросить его, если не на его финальную позицию, то близко к ней? Это бы сильно уменьшило количество ненужных сравнений.

Принцип работы:

1. Выбор опорного элемента (pivot):

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

2. Разделение (partitioning):

Перемещаем все элементы, меньшие опорного, в левую часть массива, а все элементы, большие опорного, — в правую часть. В результате опорный элемент оказывается на своём окончательном месте в отсортированном массиве.

3. Рекурсивное применение:

Рекурсивно применяем процесс к левому и правому подмассивам, не включая опорный элемент.

Пошаговый процесс

1. Выбираем опорный элемент.
2. Перемещаем элементы, меньшие опорного, влево, а элементы, большие — вправо.
3. Рекурсивно применяем процесс к подмассивам.

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

Временная сложность:

• В худшем случае: O(n^2) — происходит, когда каждый раз выбирается наихудший опорный элемент (например, когда массив уже отсортирован).
• В среднем случае: O(n log n) — для случайно распределённых данных.
• В лучшем случае: O(n log n) — когда массив каждый раз делится на равные части.

Пространственная сложность:

O(log n) — требуется для хранения стека вызовов рекурсии, если используется хвостовая рекурсия и опорные элементы выбираются удачно.

9.2 Реализация алгоритма быстрой сортировки

Реализация на Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Базовый случай: массив с 0 или 1 элементом уже отсортирован
    
    pivot = arr[len(arr) // 2]  # Выбираем опорный элемент
    left = [x for x in arr if x < pivot]  # Элементы, меньшие опорного
    middle = [x for x in arr if x == pivot]  # Элементы, равные опорному
    right = [x for x in arr if x > pivot]  # Элементы, большие опорного
    
    return quick_sort(left) + middle + quick_sort(right)

# Пример использования:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Отсортированный массив:", sorted_arr)
# Вывод: Отсортированный массив: [1, 1, 2, 3, 6, 8, 10]

Пример работы алгоритма

Возьмём пример массива: [3, 6, 8, 10, 1, 2, 1]

Первый проход:

• Опорный элемент: 8
• Левые элементы: [3, 6, 1, 2, 1]
• Средние элементы: [8]
• Правые элементы: [10]

Рекурсивная сортировка левой части [3, 6, 1, 2, 1]:

• Опорный элемент: 1
• Левые элементы: []
• Средние элементы: [1, 1]
• Правые элементы: [3, 6, 2]

Рекурсивная сортировка правой части [3, 6, 2]:

• Опорный элемент: 6
• Левые элементы: [3, 2]
• Средние элементы: [6]
• Правые элементы: []

Рекурсивная сортировка левой части [3, 2]:

• Опорный элемент: 2
• Левые элементы: []
• Средние элементы: [2]
• Правые элементы: [3]

Результат слияния: [1, 1, 2, 3, 6] для левой части, [10] для правой части, и [8] для средней.

Итоговый отсортированный массив: [1, 1, 2, 3, 6, 8, 10]

2

Задача

Модуль 1: Python Core, 18 уровень, 8 лекция

Недоступна

Быстрая сортировка

Быстрая сортировка

Открыть

2

Задача

Модуль 1: Python Core, 18 уровень, 8 лекция

Недоступна

Выбор среднего элемента

Выбор среднего элемента

Открыть