Быстрая сортировка заданного списка в Python при печати каждого шага

Question

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

Речь идет о быстрой сортировке в PythonИ он хочет, чтобы мы создали функцию, которая быстро сортирует список при распечатке каждого шага.До сих пор я использовал метод «Понимание списка» для быстрой сортировки, но не смог выяснить, где и как разместить свои операторы печати. ​​

Вот код, который я сейчас использую:

def quick_sort(lst):
    if lst == []:   return []
    pivot = lst[0]
    left = [x for x in lst[1:] if x < pivot]
    right = [x for x in lst[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

Я пытался распечатать python quick_sort(left) + [pivot] + quick_sort(right) перед возвратом, но он печатает результаты, которые не соответствуют тому, что я хочу.Размышляя об этом, это имеет смысл, поскольку метод «Понимание списка» пытается, вроде, отсортировать список, разделив его на части, и моя функция повторно вызывает себя на каждом меньшем разделе, пока в нем не останется элементов.

Я ожидаю, что при вводе списка, например, [5, 1, 4, 3, 2], программа должна по крайней мере распечатать шаги следующим образом (предположим, что я принимаю первый элемент как сводный):

>>> Enter the list: 5, 1, 4, 3, 2

[1, 4, 3, 2, 5] 5 - это поворот, меньшие значения влево, теперь нужно отсортировать [1, 4, 3, 2]

[1, 4, 3, 2, 5] 1 - это поворот, большие значения вправо, теперь [4, 3, 2] следуетбыть отсортированными

[1, 3, 2, 4, 5] 4 - сводный, меньшие значения слева, теперь [3, 2] должен быть отсортирован

[1, 2, 3, 4, 5] 3 - сводный, меньшие значения слева, теперь [2] должен быть отсортирован

[1, 2, 3, 4, 5] 2 - это сводка, никаких значений не осталось, возвращается [] и выход из рекурсии

Возможно, это можно сделать, определив другую функцию, которая будет хранить дополнительнуюсписок и обновлять его каждый раз, когда рекурсияслучается в quick_sort(), но я пока не могу думать об этом.

Answer 1

Ваш инструктор сделал неверное предположение: вы будете реализовывать быструю сортировку как сортировку на месте, а не «разделяй и властвуй», которую вы использовали.Это предположение на месте имеет значение , поскольку оно выполняет намного меньше перемещения данных: ваша процедура создает три новых списка при каждом вызове, а не просто заменяет элементы списка по мере необходимости.Однако, вот частичная попытка смягчить вашего инструктора, выделив ваш метод:

def quick_sort(lst):
    if lst == []:   return []
    pivot = lst[0]
    left = [x for x in lst[1:] if x < pivot]
    right = [x for x in lst[1:] if x > pivot]
    print(lst, pivot, "is pivot", left, "and", right, "should be sorted")
    new_list = quick_sort(left) + [pivot] + quick_sort(right)
    print("NEW", new_list)
    return new_list

quick_sort([4, 1, 5, 3, 2])