Ответ
Быстрая сортировка (QuickSort) имеет следующую сложность:
- Средний и лучший случай: O(n log n). Достигается при хорошем (близком к медиане) выборе опорного элемента (pivot).
- Худший случай: O(n²). Происходит при постоянном выборе наихудшего опорного элемента (например, минимального или максимального), что превращает алгоритм в подобие сортировки выбором.
Оптимизации для избегания худшего случая:
- Рандомизированный выбор pivot.
- Выбор медианы трех элементов (первого, среднего, последнего).
Пример реализации на Swift:
func quickSort<T: Comparable>(_ array: [T]) -> [T] {
guard array.count > 1 else { return array }
// Выбор опорного элемента (здесь — средний)
let pivot = array[array.count / 2]
// Разделение на три части
let less = array.filter { $0 < pivot }
let equal = array.filter { $0 == pivot }
let greater = array.filter { $0 > pivot }
// Рекурсивная сортировка и объединение
return quickSort(less) + equal + quickSort(greater)
}
let sorted = quickSort([3, 1, 4, 1, 5, 9, 2, 6])
print(sorted) // [1, 1, 2, 3, 4, 5, 6, 9]Примечание: Данная реализация для наглядности, но не оптимальна по памяти из-за создания множества новых массивов.
Ответ 18+ 🔞
Давай разжую эту тему про быструю сортировку, чтобы даже у мартышлюшки с одним полушарием всё встало на свои места. Ситуация, в общем-то, простая, но с подвохом, как всегда.
Вот смотри, QuickSort — это как если бы ты взял кучу носков, выбрал один наугад и сказал: «Все, что хуёвее этого — налево, все, что охуеннее — направо, а такие же — в серединку». Потом с каждой кучкой повторяешь тот же трюк. В лучшем и среднем раскладе, когда тебе везёт с выбором этого центрального носка (pivot), ты разбираешь эту кучу за O(n log n). Быстро, эффективно, все довольны.
Но есть же, блядь, и худший случай! O(n²), ёпта! Это когда тебе на каждом шагу невезуха, и ты постоянно хватаешь самый потрёпанный или самый новенький носок из кучи. Получается, что одна кучка у тебя — огромная, а вторая — пустая. И ты тупо перебираешь всё по одному элементу, как дебил. Это пиздец как медленно, почти как сортировка пузырьком в плохом настроении.
Как не наступить на эти грабли? Да элементарно, Ватсон!
- Рандомизация. Хватай pivot не по порядку, а как бог на душу положит. Случайность — наша подруга, она обычно не подводит.
- Медиана трёх. Ну или не будь лохом — посмотри на первый, средний и последний элемент, и выбери из них середнячка. Шансы налажать резко падают.
А вот тебе пример кода на Swift, смотри, не запороть бы:
func quickSort<T: Comparable>(_ array: [T]) -> [T] {
guard array.count > 1 else { return array }
// Выбор опорного элемента (здесь — средний)
let pivot = array[array.count / 2]
// Разделение на три части
let less = array.filter { $0 < pivot }
let equal = array.filter { $0 == pivot }
let greater = array.filter { $0 > pivot }
// Рекурсивная сортировка и объединение
return quickSort(less) + equal + quickSort(greater)
}
let sorted = quickSort([3, 1, 4, 1, 5, 9, 2, 6])
print(sorted) // [1, 1, 2, 3, 4, 5, 6, 9]Только не обосрись с восторга — эта реализация красивая для учебника, но по памяти она жрёт, как не в себя, потому что плодит кучу новых массивов на каждом шагу. Для продакшена надо крутить всё на месте, но это уже другая история, блядь. Главное — принцип уловил.