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

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

0 голосов
/ 11 июня 2018

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

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)

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

1 Ответ

0 голосов
/ 11 июня 2018

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

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

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

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 вместе с индексами запуска и остановки вместо копий для первой половины процесса, а затем копирование только в конце во время слияния.

...