Как я могу решить эту ошибку рекурсии в сортировке слиянием? - PullRequest
Новая
       44

Как я могу решить эту ошибку рекурсии в сортировке слиянием?

0 голосов
/ 06 июня 2019

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

Я пытаюсь реализовать сортировку слиянием, как описано здесь в этом курсе - https://www.coursera.org/learn/algorithms-part1/lecture/ARWDq/mergesort (минута 7 -10).

В настоящее время я сталкиваюсь с RecursionError

Я уже написал код на python (с огромной помощью других людей в этом сообществе).Вот оно - 

class merge_sort:

    aux_array = []                               

    def __init__(self, data):
        self.data = data
        self.aux_array = [0 for i in range(len(data))]  

    def merge(self, low, mid, high):             

        for k in range(low, high):
            self.aux_array[k] = self.data[k]            

        if( low == high):
            self.data[low] = self.aux_array[low]
            return


        i = low
        j = mid + 1
        for k in range(low, high):
            if(i > mid):
                self.data[k] = self.aux_array[j]        
                j = j + 1
            elif(j > high):
                self.data[k] = self.aux_array[i]        
                i = i + 1
            elif(self.aux_array[i] < self.aux_array[j]):
                self.data[k] = self.aux_array[i]        
                i = i + 1
            else:
                self.data[k] = self.aux_array[j]        
                j = j + 1

        return

    def mergesort(self,low, high):

        if(low < high):
            mid = (high - low)//2
            self.mergesort(low, mid)              
            self.mergesort(mid+1, high)           
            self.merge(low, mid, high)            
        else:
            return

    def start_sort(self):
        high = len(self.data) - 1
        self.mergesort(0, high)


arr = [10, 2, 30, 0, 4]

arr1 = merge_sort(arr)
arr1.start_sort()
print(arr1)

Это точная ошибка - 

Traceback (most recent call last):
  File "new_sorting.py", line 55, in <module>
    arr1.start_sort()
  File "new_sorting.py", line 49, in start_sort
    self.mergesort(0, high)
  File "new_sorting.py", line 42, in mergesort
    self.mergesort(mid+1, high)
  File "new_sorting.py", line 42, in mergesort
    self.mergesort(mid+1, high)
  File "new_sorting.py", line 42, in mergesort
    self.mergesort(mid+1, high)
  [Previous line repeated 993 more times]
  File "new_sorting.py", line 41, in mergesort
    self.mergesort(low, mid)
  File "new_sorting.py", line 39, in mergesort
    if(low < high):
RecursionError: maximum recursion depth exceeded in comparison

Ответы [ 2 ]

0 голосов
/ 07 июня 2019

Исправления, отмеченные в комментариях: 

class merge_sort:

    def __init__(self, data):
        self.data = data                            # reference to data
        self.aux_array = [0] * len(data)            # allocate aux_array

    def merge(self, low, mid, high):
        for k in range(low, high+1):                # fix (high+1)
            self.aux_array[k] = self.data[k]
        i = low
        j = mid + 1
        for k in range(low, high+1):                # fix (high+1)
            if(i > mid):
                self.data[k] = self.aux_array[j]
                j = j + 1
            elif(j > high):
                self.data[k] = self.aux_array[i]
                i = i + 1
            elif(self.aux_array[i] < self.aux_array[j]):
                self.data[k] = self.aux_array[i]
                i = i + 1
            else:
                self.data[k] = self.aux_array[j]
                j = j + 1

    def mergesort(self, low, high):
        if(low >= high):
            return
        mid = low + (high - low)//2                 # fix (low + )
        self.mergesort(low, mid)
        self.mergesort(mid+1, high)
        self.merge(low, mid, high)

    def start_sort(self):
        high = len(self.data) - 1
        self.mergesort(0, high)

arr = [10, 2, 30, 0, 4]
#arr1.data will be a reference to arr
arr1 = merge_sort(arr)
arr1.start_sort()
print(arr)                                          # fix (arr not arr1)
0 голосов
/ 07 июня 2019

Математическая ошибка: 

mid = (high - low)//2

Средняя точка фактически является средним значением двух чисел: 

mid = (high + low)//2

Также проверьте граничное условие, когда high = low + 1

...