Быстрая сортировка на языке Python

Быстрая сортировка (quick sort) - это один из самых известных и широко используемых алгоритмов сортировки. Он основан на принципе "разделяй и властвуй".

Алгоритм быстрой сортировки следующий:

1. Выбирается опорный элемент из исходного массива (обычно это первый или последний элемент).

2. Остальные элементы массива распределяются по двум подмассивам: одни элементы меньше опорного, другие - больше опорного.

3. Рекурсивно вызывается быстрая сортировка для двух подмассивов.

4. Отсортированные подмассивы объединяются в один отсортированный массив.

Вот пример кода на Python, демонстрирующий реализацию быстрой сортировки:

python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)
    
# Пример использования    
array = [5, 2, 9, 1, 0, 8, 4, 7, 3, 6]
sorted_array = quick_sort(array)
print(sorted_array)

В данном примере массив `[5, 2, 9, 1, 0, 8, 4, 7, 3, 6]` будет отсортирован с использованием быстрой сортировки. Отсортированный массив будет равен `[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]`.

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