пытается реализовать быструю сортировку с использованием Python, но это не работает

Question

Я пытаюсь реализовать алгоритм быстрой сортировки с использованием Python. Я думаю, что сделал все правильно, но кажется, что есть проблема с моим кодом, каждый раз, когда я запускаю код, он не работает, пожалуйста, вы можете помочь мне найти проблемус моим кодом.

def quicksort(alist,first,last):
    if first < last:
        split = partition(alist,first,last)

        quicksort(alist,first,split-1)
        quicksort(alist,split+1,last)



def partition(arr,first,last):

    pivot_val = arr[first]
    rightmark = first +1
    leftmark = last

    done = False

    while not done:

        while leftmark <= rightmark and arr[leftmark] <= pivot_val:
            leftmark +=1
        while arr[rightmark] >= pivot_val and rightmark >= leftmark:
            rightmark -=1

        if rightmark < leftmark:
            done = True
        else:
            tmp = arr[leftmark]
            arr[leftmark] = arr[rightmark]
            arr[rightmark] = tmp


    tmp = arr[rightmark]
    arr[rightmark] = arr[first]
    arr[first] = tmp

    return rightmark


lst = [22,54,33,11,87,76,1,3]

quicksort(lst,0,len(lst)-1)

print(lst)

вывод выглядит так:

[54, 22, 11, 33, 76, 87, 1, 3]

Answer 1

Да, обычная реализация имеет стержень в качестве последнего значения, а не первое, но это не имеет значения.Ошибка, однако, заключается в инициализации правой и левой меток.Предполагая, что левая метка находится слева, т. Е. Меньше, а правая метка больше, тогда левая метка должна быть инициализирована до первого + 1, а правая метка должна быть инициализирована до последнего.

Это не нормальная реализация быстрой сортировки, чьяФункция разбиения просто циклически линейно проходит по массиву (кроме разворота).Он ловко перемещает левую метку вправо до тех пор, пока первая запись не станет больше, чем точка поворота, затем перемещает правую метку влево до первой записи, которая меньше точки поворота.Затем он меняет эти два значения, пока они не пересекутся.Это конечное условие.