Алгоритм быстрой сортировки в Python

Всем привет, добро пожаловать на programminginpython.com. Здесь я покажу вам, как реализовать алгоритм быстрой сортировки в Python. В предыдущих статьях я рассмотрел Сортировку вставкой, Сортировку слиянием, Сортировку по выбору и Сортировку пузырьков. Теперь давайте научимся реализовывать еще один алгоритм сортировки - алгоритм быстрой сортировки.

Quicksort - это алгоритм сортировки на месте, что означает, что он не требует какого-либо дополнительного / временного списка для выполнения сортировки, все будет выполнено с самим исходным списком. Здесь, в этой технике сортировки, мы выберем элемент поворота и расположим все элементы справа больше, чем элементы поворота, а элементы слева меньше, чем элементы поворота. Мы снова делаем тот же шаг для левого и правого элементов сводной таблицы в качестве подсписок, пока все элементы не будут отсортированы.

Быстрая сортировка, если она реализована правильно, является одним из лучших алгоритмов сортировки. Фактически, функция сортировки, предоставляемая в большинстве языковых библиотек, является реализацией самой быстрой сортировки.

Сложность быстрой сортировки по времени

Лучший случайO (n log n)

Средний случай O (n log n)

Худший случай O (n2)

Алгоритм:

1. Выберите элемент, называемый точкой поворота, из массива.
2. Секционирование: измените порядок массива так, чтобы все элементы со значениями, меньшими, чем точка поворота, располагались перед точкой поворота, а все элементы со значениями, превышающими точку поворота, располагались после нее (равные значения могут быть в любом случае). После этого разбиения стержень находится в окончательном положении. Это называется операцией разбиения.
3. Рекурсивно примените вышеуказанные шаги к подмассиву элементов с меньшими значениями и отдельно к подмассиву элементов с большими значениями.

Программа:

def partition(sort_list, low, high):
    i = (low -1)
    pivot = sort_list[high]
    for j in range(low, high):
        if sort_list[j] <= pivot:
            i += 1
            sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
    sort_list[i+1],sort_list[high] = sort_list[high], sort_list[i+1]
    return (i+1)
            
def quick_sort(sort_list, low, high):
    if low < high:
        pi = partition(sort_list, low, high)
        quick_sort(sort_list, low, pi-1)
        quick_sort(sort_list, pi+1, high)
lst = []
size = int(input("Enter size of the list: "))
for i in range(size):
    elements = int(input("Enter an element"))
    lst.append(elements)
low = 0
high = len(lst) - 1
quick_sort(lst, low, high)
print(lst)

Вот и все, мы успешно реализовали алгоритм быстрой сортировки.

Не стесняйтесь взглянуть на некоторые другие алгоритмы здесь или на некоторые программы в списках здесь или взгляните на все программы на python здесь.

Сообщение: https://programminginpython.com/quick-sort-algorithm-python/

Https://programminginpython.com/quick-sort-algorithm-python/

YouTube: https://www.youtube.com/watch?v=hxEBHcwqwSo

GitHub: https://github.com/avinashn/programminginpython.com/blob/master/Algorithms/Sorting%20Algorithms/quick_sort.py