Ошибка быстрой сортировки после первой рекурсии? - PullRequest
2 голосов
/ 20 июня 2020

Я уже реализовал некоторую реализацию быстрой сортировки, но она создает 2 новых списка для каждой рекурсии, поэтому я хотел работать со списком напрямую, но по какой-то причине изменения, внесенные в список после первой рекурсии, не отражаются в окончательном списке.

Рассматриваемый код:

def quicksort(lista: list, min_lenght=3):

    def part(listb: list) -> list:
        pivot = listb[0]
        low = 0
        mid = 0
        high = len(listb) - 1
        while mid <= high:

            if listb[mid] < pivot:
                listb[low], listb[mid] = listb[mid], listb[low]
                low += 1
                mid += 1
            elif listb[mid] > pivot:
                listb[mid], listb[high] = listb[high], listb[mid]
                high -= 1
            else:
                mid += 1
        return [low, mid]

    if len(lista) <= min_lenght:
        lista.sort()
    else:
        lowmark, midmark = part(lista)

        quicksort(lista[:lowmark])
        quicksort(lista[midmark:])


lol = [5, 9, 8, 7, 6, 10, 4, 3, 25]
print(lol)
quicksort(lol)
print(lol)
...