Быстрая сортировка
Выбирает одно значение, опорный элемент, и ставит меньшие значения слева от него, а большие справа. Потом делает то же самое с каждой частью.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- нет
- да
Лучший случай: как растёт время с размером списка n, когда входные данные самые удобные для алгоритма.
Средний случай: обычный рост времени с n. При n² вдвое больше значений сортируются вчетверо дольше; n log n растёт намного медленнее.
Худший случай: рост времени на самых неудобных данных. Важно, когда скорость не должна падать никогда.
Память: сколько памяти нужно сверх самого списка. 1 значит несколько переменных, n значит копию списка.
Стабильное: равные значения сохраняют исходный порядок. Это важно, когда записи сортируют по одному полю.
Без дополнительной памяти: сортирует внутри самого списка, без второго списка.
- сравнение
- перемещение
- опорный элемент
- на окончательном месте
Попробуйте: Выберите обратный список. Опорный элемент всегда наименьший или наибольший из оставшихся, поэтому одна часть пуста, а затраты растут к n².
Как это работает
Здесь опорный элемент - последнее значение диапазона. Идём слева направо и каждое значение, не большее опорного, обменом переносим в левую часть. Затем опорный элемент встаёт между двумя частями и остаётся там навсегда. Дальше каждую часть сортируем так же.
Когда стоит применять
На практике один из самых быстрых способов сортировки, и дополнительной памяти почти не требует. Но если опорный элемент раз за разом неудачный, например на уже отсортированном списке, сортировка становится медленной. Поэтому на практике опорный элемент выбирают тщательнее.