Предыдущие части: Алгоритм quicksort – один из наиболее распространённых "промышленных" алгоритмов, он используется в библиотеках многих языков программирования. И это заслуженно: он наиболее универсальный и достаточно быстрый. Но и у него есть слабые места. Как работает quicksort В массиве, который нужно отсортировать, выбирается какой-нибудь элемент (любой). Он называется опорным (pivot). Затем мы проходим по массиву, и все элементы, которые меньше опорного, размещаем слева от него, а все, которые больше – справа...

Заметки: Эта сортировка намного быстрее сортировки выбором (когда делим пополам всегда). И используется во многих библиотеках (например, метод sort). Но и понять её гораздо сложнее. Тут уже прям придётся вникать. Сложность зависит от выбора опорного элемента. В худшем будет O(n^2). В лучшем и в среднем — O(n logn). Существует ещё сортировка слияниям и она по сложности примерно такая же. Тогда почему быстрая сортировка считается...

В этой статье поговорим о Быстрой сортировке (quicksort). Почему именно она?