Рекурсия в Python / Сортировка слиянием / Вызов по ссылке - PullRequest
Новая
       6

Рекурсия в Python / Сортировка слиянием / Вызов по ссылке

0 голосов
/ 04 декабря 2018

Мои извинения, я новичок в StackOverFlow & Python.Я написал код для Merge_Sort, но он не работает, так как значения массивов теряются при возврате из рекурсивных вызовов.
Среда кодирования: Python3.x
ОС: Linux (Ubuntu 18.04)
Ниже мой код: 

class sort: 
def __init__(self, arr, n):
    self.arr = arr
    self.n = n   
def __init__(self, arr, m, n):
    self.arr = arr
    self.m = m
    self.n = n
    arrS = arr.copy()
    arrL = [0] * (n - int((m + n)/2) + 1)
    arrR = [0] * (n - (m + 1))
def Merge_sort(self,arr,first,last):
    mid = int((first + last) / 2)
    arrMain = arr[first:last+1]
    arrLeft = arr[first:mid+1]
    arrRight = arr[mid+1:last+1]
    arrL = [0] * (mid - first + 1)
    arrR = [0] * (last - mid + 1)
    arrN = [0] * ( last - first + 1)
    if first < last:
        #Sort Left Array
        self.Merge_sort(arr, first, mid)
        #Sort Right Array
        self.Merge_sort(arr, mid+1, last)
        #I defined the below 3 variables while debugging to view the list
        arrL = arr[first:mid+1]
        arrR = arr[mid+1:last+1]
        print("Left Array: " + str(arrL))
        print("Right Array: " + str(arrR))
        x = len(arrL)
        y = len(arrR)
        i = j = k = 0
        while i < x and j < y:
            if (arrL[i] <= arrR[j]):
                arrN[k] = arrL[i]
                i += 1
            else:
                arrN[k] = arrR[j]
                j += 1
            # end-if#001
            k += 1
        while (i < x):
            arrN[k] = arrL[i]
            i += 1
            k += 1
        while (j < y):
            arrN[k] = arrR[j]
            j += 1
            k += 1
        arr = arrN.copy()
        print("Merged Array:" + str(arr))
        return arrN
    #End-if#001
from Sort import sort
arr = [7, 5, 4 ,9, 3, 2 , 0, 1, 6, 8]
n = 0
sort4 = sort(arr, 0, int(len(arr)))
sort4.arr = arr.copy()
sort4.Merge_sort(sort4.arr, 0, int(len(arr)) - 1)

Ввод программы: arr = [7, 5, 4, 9, 3, 2, 0, 1, 6, 8]
Вывод программы: Левый массив: [7, 5, 4, 9, 3] Правый массив: [2, 0, 1, 6, 8]
Объединенный массив: [2, 0, 1, 6,7, 5, 4, 8, 9, 3]
В конце программы, похоже, просто сливается мой исходный массив.
Пожалуйста, предложите.

1 Ответ

0 голосов
/ 04 декабря 2018

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

def Merge_sort(self,arr,first,last):

    mid = int((first + last) / 2)

    arrMain = arr[first:last+1]
    arrLeft = arr[first:mid+1]
    arrRight = arr[mid+1:last+1]
    arrL = [0] * (mid - first + 1)
    arrR = [0] * (last - mid + 1)
    arrN = [0] * ( last - first + 1)

    if first < last:

        #Sort Left Array
        arrL = self.Merge_sort(arr, first, mid)

        #Sort Right Array
        arrR = self.Merge_sort(arr, mid+1, last)

        #arrL = arr[first:mid+1]
        #arrR = arr[mid+1:last+1]
        print("Left Array: " + str(arrL))
        print("Right Array: " + str(arrR))
        x = int(len(arrL))
        y = int(len(arrR))

        i = j = k = 0

        while i < x and j < y:
            if (arrL[i] <= arrR[j]):
                arrN[k] = arrL[i]
                i += 1
            else:
                arrN[k] = arrR[j]
                j += 1
            # end-if#001
            k += 1

        while (i < x):
            arrN[k] = arrL[i]
            i += 1
            k += 1

        while (j < y):
            arrN[k] = arrR[j]
            j += 1
            k += 1

        arr = arrN.copy()

        print("Merged Array:" + str(arr))

        return arrN
    #End-if#001
    return arrMain
...