Быстрая сортировка в Python
Значения делятся на меньшие, равные и большие опорного.
Что такое Быстрая сортировка в Python?
Значения делятся на меньшие, равные и большие опорного.
Разделяйте значения вокруг опорного элемента.
Когда это использовать?
- Понимать алгоритмы и структуры данных.
- Наблюдать каждый шаг и проверять граничные случаи.
- Сравнивать время работы и память.
Визуализация: Быстрая сортировка в Python
O(n log n)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
main.py
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))Ожидаемый результат
[1, 5, 7, 8, 9, 10]Как это работает
Среднее время O(n log n), но при неудачном выборе возможно O(n²).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.