Быстрая сортировка (quicksort)

Коротко: Быстрая сортировка — быстрый метод сортировки на основе «разделяй и властвуй»: выбирает опорный элемент, делит список на меньшие и большие значения и рекурсивно сортирует обе части.

Подробнее: В среднем быстрой сортировке нужно O(n log n) шагов, и обычно она сортирует прямо в имеющейся памяти. В худшем случае (неудачный выбор опорного элемента на уже отсортированных данных) — O(n²). Случайный или срединный выбор опорного элемента на практике это предотвращает.

Подробности

def quicksort(items):
    if len(item

См. также: сортировка слиянием, сортировка пузырьком, сортировка, О-нотация