Быстрая сортировка . Лимит памяти

Question

Есть задача написать код эффективной сортировки под конкретную задачу и этот код должен пройти тесты в котором есть определенные ограничения, например по времени выполнения и по лимиту памяти. Пока мой код не проходит по лимиту памяти. Я как понимаю память начинает много потреблять при разделении элементов на группы, но как улучшить код пока не понимаю. Я новичок и только учусь и для меня трудно даются алгоритмы, подскажите пожалуйста как можно еще улучшить код чтобы меньше потребляла памяти?

def partition(competitors, left, right):
    if right <= left:
        return
    pivot = (left + right) // 2
    part = competitors[pivot]
    begin = left
    end = right
    while begin <= end:
        while part > competitors[begin]:
            begin += 1
        while part < competitors[end]:
            end -= 1
        if begin <= end:
            competitors[begin], competitors[end] = competitors[
                end], competitors[begin]
            begin += 1
            end -= 1
    partition(competitors, left, end)
    partition(competitors, begin, right)


def transformations(competitors):
    competitors[1] = - int(competitors[1])
    competitors[2] = int(competitors[2])
    return [competitors[1], competitors[2], competitors[0]]


def quick_sort(competitors):
    partition(competitors, 0, len(competitors) - 1)
    return [line[2] for line in competitors]


if __name__ == '__main__':
    number = int(input())
    competitors = [transformations(input().split()) for _ in range(number)]
    result = quick_sort(competitors)
    print(*result, sep="\n")

Answer 1

Быстрая сортировка выполняется in-place, т.е. не требует дополнительного места для хранения массива. Ей, однако, нужно место в стеке для хранения состояния, размер этого места зависит от глубины рекурсии, и при неудачном разделении размер стека может быть сравним с размером массива. Чтобы этого избежать, можно рекурсивный вызов делать только для более короткой части, а длинную обрабатывать тут же. В таком случае глубина стека не превысит log(n)

Примерно так модифицировать ваш код (не проверял):

def partition(competitors, left, right):
    while right > left:
        pivot = (left + right) // 2
        part = competitors[pivot]
        begin = left
        end = right
        while begin <= end:
            while part > competitors[begin]:
                begin += 1
            while part < competitors[end]:
                end -= 1
            if begin <= end:
                competitors[begin], competitors[end] = competitors[
                    end], competitors[begin]
                begin += 1
                end -= 1
        if end - left < right - begin:
            partition(competitors, left, end)
            left = begin
        else:
            partition(competitors, begin, right)
            right = end

БЛОГ НА HUSL

Быстрая сортировка . Лимит памяти

Ответы (1 шт):