Python: передача списка в качестве параметра, чтобы отсортировать фактический список

Question

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

def mergeSort(L, ascending = True):
    print('Mergesort, Parameter L:')
    print(L)
    result = []
    if len(L) == 1: 
        return L 
    mid = len(L) // 2 
    teilliste1 = mergeSort(L[:mid], ascending)
    teilliste2 = mergeSort(L[mid:], ascending)
    x, y = 0, 0
    while x < len(teilliste1) and y < len(teilliste2): 
        if (ascending and teilliste1[x] > teilliste2[y]) or (not ascending and teilliste1[x] < teilliste2[y]):
            result.append(teilliste2[y])  
            y = y + 1  
        else:
            result.append(teilliste1[x]) 
            x = x + 1  
    result = result + teilliste1[x:] 
    result = result + teilliste2[y:]
    return result

liste1 = list([3, 2, -1, 9, 17, 4, 1, 0])
mergeSort(liste1)
print(liste1) # result will be the unsorted list

Что мне нужно изменить в функции, чтобы она вызывала по значению и сортировала фактический список?

Я знаю, что мог сделать

mergeResult = mergeSort(liste1)
print(mergeResult)

но, видимо, я должен изменить исходный список параметров.

Answer 1

Существует два основных способа написания рекурсивной функции декомпозиции. Неизменяемая версия вызывает себя на копиях двух меньших частей, затем собирает и возвращает их; это то, что вы написали. Изменяемая версия вызывает себя на фактическом вводе, затем изменяет это на месте и ничего не возвращает; это то, что ваш учитель хочет здесь.

Обратите внимание, что, в отличие от некоторых других алгоритмов сортировки, сортировка слиянием не может быть выполнена с постоянным дополнительным хранилищем, только лучше, чем линейное дополнительное хранилище. (Логарифмический вариант возможен, но сложен; я сомневаюсь, что ваш учитель настаивает на этом.) И из-за этого большинство алгоритмов сортировки слиянием, которые вы найдете в книгах, Википедии и т. Д., Будут написаны как сортирующие, а не сортируемые по месту. Это означает, что это, вероятно, небольшой вопрос с подвохом, пытаясь понять, можете ли вы выяснить, как преобразовать хорошо известную копирующую версию алгоритма в версию на месте с явным дополнительным хранилищем.

---

Вы всегда можете написать неизменный алгоритм, а затем изменить его в самом конце, например:

def _mergesort(L, ascending):
    # your existing code

def mergesort(L, ascending=True):
    L[:] = _mergesort(L, ascending)

Это дает вам все издержки неизменности без преимуществ. Но это означает, что вы можете написать множество функций сортировки с одним и тем же API, которые все реализованы на месте, если это разумная оптимизация, но не если это не так, что, похоже, является тем, к чему стремится ваш учитель.

---

Если вам не нужна функция-оболочка, вы можете изменить последнюю строку с:

return result

… Чтобы:

L[:] = result

Однако, поскольку это меняет API, вам также необходимо изменить свои рекурсивные вызовы, чтобы они соответствовали. Например, вы можете сделать это:

teilliste1 = L[:mid]
mergeSort(teilliste1, ascending)
teilliste2 = L[mid:]
mergeSort(teilliste2, ascending)

---

В Python мутирующая функция рекурсивной декомпозиции часто работает, передавая индексы начала и конца вместе со списком, например так:

def mergesort(L, ascending=True, start=None, stop=None):
    if start is None: start = 0
    if stop is None: stop = len(L)

    if stop - start <= 1:
        return

    mid = (stop - start) // 2 + start 
    mergeSort(L[start:mid], ascending)
    mergeSort(L[mid:stop], ascending)

    # etc.

Как упомянуто выше, этап слияния потребует некоторого вспомогательного хранения. Самое простое, что можно сделать - и, вероятно, достаточно хорошо для вашего назначения, даже если это означает линейное пространство, - это просто создать левый список и правый список, а затем назначить их обратно в L[start:mid], L[mid:stop] = left, right,

Обратите внимание, что это не так уж и отличается от L[:] = result версия выше; это действительно просто вопрос использования L сам, вместе с индексами запуска и остановки, вместо копий для первой половины процесса, а затем копируется только в конце во время слияния.