Рекурсия в Python 3 - PullRequest
Новая
       20

Рекурсия в Python 3

0 голосов
/ 21 сентября 2018

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

Вывод приведенного ниже кода: - 

[9, 5]
After merging [5, 9]
[12, 4]
After merging [4, 12]
[9, 5, 12, 4] #it should be (the updated one i.e  [5, 9, 4, 12])
After merging [5, 9, 12, 4]
[6, 8]
After merging [6, 8]
[45, 2]
After merging [2, 45]
[6, 8, 45, 2]
After merging [6, 8, 45, 2]
[9, 5, 12, 4, 6, 8, 45, 2]
After merging [4, 5, 6, 8, 9, 12, 45, 2]
[9, 5, 12, 4, 6, 8, 45, 2]

def merge(arr1, arr2):
"""
Input is two sorted lists
Output is a single merged list
"""
        for i in arr1:
            for j in list(range(len(arr2))):
                if i<arr2[j]:
                    arr2.append(arr2[-1])
                    for count in list(range(len(arr2)-1, j, -1)):
                        arr2[count] = arr2[count-1]
                    arr2[j] = i
                    break
                if j == len(arr2)-1:
                    arr2.append(i)
        return arr2
    def mergeSort(arr):
        if len(arr) !=1:
            mergeSort(arr[:len(arr)//2])
            mergeSort(arr[len(arr)//2:])
            print(arr)
            arr = merge(arr[:len(arr)//2],arr[len(arr)//2:])
            print("After merging", arr)

        else:
            return arr
    a = [9,5,12, 4, 6, 8,45, 2]
    mergeSort(a)
    print(a)

Ответы [ 2 ]

0 голосов
/ 21 сентября 2018

Я делаю ооочень небольшие изменения, поэтому код остается вашим, благодаря вашим усилиям, вы были так близко, посмотрите:

Дело в том, что после просмотра кода вы должны передать две половинки слияниюметод, а также проверьте, если он пуст.Кроме того, значительно лучше возвращать результаты, а не вносить изменения на месте - 

def merge(arr1, arr2):
        for i in arr1:
            for j in list(range(len(arr2))):
                if i<arr2[j]:
                    arr2.append(arr2[-1])
                    for count in list(range(len(arr2)-1, j, -1)):
                        arr2[count] = arr2[count-1]
                    arr2[j] = i
                    break
                if j == len(arr2)-1:
                    arr2.append(i)
        return arr2
def mergeSort(arr):
    if len(arr) !=1 and len(arr):
        ary1 = mergeSort(arr[:len(arr)//2])
        ary2 = mergeSort(arr[len(arr)//2:])
        print(arr)
        ary3 = merge(ary1,ary2)
        print("After merging", ary3)
        return ary3
    else:
        return arr
a = [9,5,12, 4, 6, 8,45, 2]

print(mergeSort(a))

, вывод 

[9, 5]
After merging [5, 9]
[12, 4]
After merging [4, 12]
[9, 5, 12, 4]
After merging [4, 5, 9, 12]
[6, 8]
After merging [6, 8]
[45, 2]
After merging [2, 45]
[6, 8, 45, 2]
After merging [2, 6, 8, 45]
[9, 5, 12, 4, 6, 8, 45, 2]
After merging [2, 4, 5, 6, 8, 9, 12, 45]
[2, 4, 5, 6, 8, 9, 12, 45]
0 голосов
/ 21 сентября 2018

Вы должны заставить mergeSort вернуть объединенный список, и вызывающая сторона должна вывести возвращаемое значение mergeSort вместо: 

def merge(arr1, arr2):
    merged = []
    while arr1 and arr2:
        if arr1[0] > arr2[0]:
            arr1, arr2 = arr2, arr1
        merged.append(arr1.pop(0))
    merged.extend(arr1 or arr2)
    return merged
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    return merge(mergeSort(arr[:len(arr)//2]), mergeSort(arr[len(arr)//2:]))
a = [9, 5, 12, 4, 6, 8, 45, 2]
print(mergeSort(a))
...