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