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

Программа будет сортировать список методом быстрой сортировки (QuickSort).

Суть сортировки:

1. Выбрать опорный элемент из массива. Обычно опорным элементом является средний элемент.
2. Разделить массив на два подмассива: элементы меньше опорного и элементы больше опорного.
3. Рекурсивно применить сортировку к двум подмассивам.

Сложность сортировки по времени:

1. Худшая O(n^2)
2. Средняя O(n * log2n)
3. Лучшая O(n * 2log 2n)

Шаги к правильному решению

1. Создадим функцию quicksort, которая принимает на вход список и 2 переменные: start и end.
2. Если end-start не больше 1, выходим.
3. Найдем индекс опорного элемента p, p = partion(alist, start, end).
4. Вызовем quicksort(alist, start, p).
5. Вызовем quicksort(alist, p + 1, end).
6. Определим функцию partition, которая принимает список и 2 параметра: start, end.
7. Функция partition использует схему разбиения Хоара.

def quicksort(alist, start, end):
    '''Sorts the list from indexes start to end - 1 inclusive.'''
    if end - start > 1:
        p = partition(alist, start, end)
        quicksort(alist, start, p)
        quicksort(alist, p + 1, end)
 
 
def partition(alist, start, end):
    pivot = alist[start]
    i = start + 1
    j = end - 1
 
    while True:
        while (i <= j and alist[i] <= pivot):
            i = i + 1
        while (i <= j and alist[j] >= pivot):
            j = j - 1
 
        if i <= j:
            alist[i], alist[j] = alist[j], alist[i]
        else:
            alist[start], alist[j] = alist[j], alist[start]
            return j
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
quicksort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)