Быстрая сортировка Python: преимущества и основные принципы работы

Быстрая сортировка, или QuickSort, это один из наиболее распространенных алгоритмов сортировки в Python. Он имеет временную сложность O(n log n) в лучшем и среднем случаях, и O(n^2) в худшем случае. Однако, в среднем его скорость работы превосходит другие алгоритмы сортировки.

Пример кода, демонстрирующего быструю сортировку в Python, может выглядеть следующим образом:

python
def quicksort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)
arr = [3, 5, 12, 2, 7, 16, 20]
print(quicksort(arr))

Этот код реализует функцию QuickSort, которая принимает список arr для сортировки. Если длина списка меньше 2, то он является отсортированным, и возвращается без изменений. В противном случае, первый элемент списка выбирается в качестве опорного элемента (пивота), и все элементы, которые меньше или равны опорному, отправляются в новый список less, а все большие - в список greater.

Затем функция рекурсивно вызывает себя для less и greater, пока они не станут достаточно маленькими, чтобы быть отсортированными по возрастанию. Затем функция объединяет отсортированные less и greater списки с опорным элементом pivot, и возвращает отсортированный список.

При запуске этого кода на входе arr=[3, 5, 12, 2, 7, 16, 20], функция quicksort(arr) вернет отсортированный список [2, 3, 5, 7, 12, 16, 20].

Вывод:

Быстрая сортировка - это очень эффективный алгоритм сортировки в Python. Она может быть легко реализована в виде функции и работает в большинстве случаев быстро и надежно. Простой пример кода выше позволяет использовать QuickSort для сортировки элементов различных типов, включая числа, строки и т. Д.