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

Question

Я пытаюсь написать функцию быстрой сортировки на python, но у меня возникают проблемы с ее реализацией.Я понимаю логику, однако я никогда раньше не писал рекурсивную функцию.

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

Как и ихЕсть несколько способов сделать быструю сортировку. Я опубликую свою логику.Моя логика такова:

1. Пивот - это случайно выбранный элемент в списке
2. Пивот перемещается в крайнее правое положение в списке.
3. Затем каждый элемент в списке сравнивается с сводной точкой, чтобы определить, больше ли она, чем сводная.
4. Первый элемент, превышающий сводную, обозначается как FirstBigNumber.
5. Списокзатем повторяется снова.Первый элемент, который меньше позиции свопинга в списке с помощью FirstBigNumber, Swapped = True
6. Затем будет найден новый FirstBigNumber
7. Повторяйте шаги 4,5,6 до тех пор, пока не будет достигнута точка разворота.
8. Смена свопа с FirstBigNumber.
9. Список должен быть отсортирован.

Мой код:

import random
List=[3,5,1,7,2,8]
pivot_pos=0
def getpivot(List):
    #Get pivot position
    pivot_pos=random.randint(0,len(List)-1)
    return pivot_pos

def quicksort(List,pivot_pos):
    #Calling Get Pivot function
    getpivot(List)
    print(List)
    #Obtain pivot
    pivot=List[pivot_pos]
    print("Pivot is ",pivot)
    #Swap pivot to right of list
    List[len(List)-1],List[pivot_pos]=List[pivot_pos],List[len(List)-1]
    Swapped=True
    print(List)
    #Loop through List
    for j in range(0,len(List)-1):
        print("Checking if",List[j],"is bigger than",pivot)
        #Marks first num larger than
        if List[j]>pivot and Swapped==True:
            #FirstBigNum stores the index of the First number bigger than pivot
            FirstBigNum=List[j]
            IndexOfBigNum=j
            print("BigNum is",FirstBigNum)
            #This new Big number has not been swapped
            Swapped=False
        for i in range(0,len(List)-1):
            if List[i]<pivot:
                    #Swap the index of smaller num with first big num
                    print("Swapped",List[i]," with ",List[IndexOfBigNum])
                    List[IndexOfBigNum],List[i]=List[i],List[IndexOfBigNum]
                    print(List)
                    Swapped=True
            elif List[i]<pivot:
                print("Pivot is bigger than",List[i])
                #If Value greater than pivot
                pass
            elif i == (len(List)-1):
                #We have reached the end of the List
                #So we need to swap the pivot with the FirstBigNum
                List[FirstBigNum],List[i]==List[i],List[FirstBigNum]
                print("Here")
                print(List)
            else:
                #Is equal to pivot
                pass

getpivot(List)
quicksort(List,pivot_pos)

Вывод, который я получаю:

[5, 8, 7, 2, 1, 3] 

Вывод, который я должен получить:

[1, 2, 3, 5, 7, 8]   

Answer 1

Вот стандартная реализация Quicksort, использующая рекурсию с разделом Lomuto.Я включил основной драйвер со случайным списком, чтобы вы могли проверить его:

import random


def quick_sort(a, l=0, r=None):
    # Recusrion requires a Base Case
    if r is None :
        r = len(a) - 1
    if l >= r :
        return 0
    # If the Base Case is not encountered then proceed to partion
    s = lomuto_partition(a, l, r)
    # call quicksort recursively
    quick_sort(a, l, s-1)
    quick_sort(a, s+1, r)
    return a


def lomuto_partition(a, l, r):
    p = a[l]
    s = l
    for i in range(l+1, r+1) :
        if a[i] < p :
            s += 1
            a[s], a[i] = a[i], a[s]
    a[l], a[s] = a[s], a[l]
    return s


def random_seq(n=10, lo=0, hi=100):
    seq = []
    for i in range(n):
        seq.append(random.randint(lo, hi))
    return seq


if __name__ == '__main__' :
    n = 16
    print('n:', n)

    a = random_seq(n)
    print("Unsorted Random List: ", a)

Надеюсь, это поможет