Есть ли способ использовать возвращаемое значение в качестве аргумента той же функции во время предыдущей рекурсии в сортировке слиянием

Question

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

Вот мой код:

a = [10,5,2,20,-50,30]

def mergeSort(arr):
   l = 0
   h = len(arr)-1
   if h > l:
      mid = (l+h) // 2
      left = arr[l:mid+1]
      right = arr[mid+1:]
      mergeSort(left)
      mergeSort(right)
      merge(left, right)

def merge(l, r):
   subarr = []
   lc = 0
   rc = 0
   loop = True
   while loop:
      if lc > len(l)-1 and rc <= len(r)-1:
         for i in range(rc, len(r)):
            subarr.append(r[i])
            loop = False
      elif lc <= len(l)-1 and rc > len(r)-1:
         for i in range(lc, len(l)):
            subarr.append(l[i])
            loop = False
      elif l[lc] < r[rc]:
         subarr.append(l[lc])
         lc += 1
         loop = True
      elif r[rc] < l[lc]:
         subarr.append(r[rc])
         rc += 1
         loop = True
      elif l[lc] == r[rc]:
         subarr.append(l[lc])
         subarr.append(r[rc])
         lc += 1
         rc += 1
         loop = True    

mergeSort(a)

Любая помощь будет оценена спасибо:)

Answer 1

В нашем коде есть несколько проблем:

• вы не вернете отсортированный фрагмент из mergeSort или merge. Ваша реализация не сортирует массив на месте, поэтому вы должны вернуть subarr в merge и возвращаемое значение merge в mergeSort или arr, если длина меньше 2.

• Ваш код слишком сложен: существует множество настроек, таких как mid+1, len(l)-1 и т. Д. c. Настоятельно рекомендуется использовать значения индекса от 0 до len(arr), за исключением. Таким образом, вам не нужно добавлять подверженные ошибкам корректировки + 1 / -1.

• функция merge должна выполняться в 3 этапа: объединять левый и правый массивы до тех пор, пока оба значения индекса меньше, чем длины массива, затем добавьте оставшиеся элементы из левого массива, наконец добавьте оставшиеся элементы из правого массива.

• Нет необходимости выполнять 3 различных теста для определения из какого левого и правого массива взять следующий элемент, достаточно одного теста.

• также используют одинаковое количество пробелов для отступа блоков, 3 или 4 пробела предпочтительно, вкладки подвержены ошибкам, так как они расширяются до разного количества пробелов на разных устройствах, смешивая вкладки и пробелы, как вы это сделали, безусловно, проблема.

Вот модифицированная версия:

def mergeSort(arr):
   # no need to use l and h, use len(arr) directly
   if len(arr) > 1:
      # locate the middle point
      mid = len(arr) // 2
      # left has the elements before mid
      left = arr[:mid]
      # right has the elements from mid to the end
      right = arr[mid:]
      # sort the slices
      left = mergeSort(left)
      right = mergeSort(right)
      # merge the slices into a new array and return it
      return merge(left, right)
   else:
      # return the original array (should actually return a copy)
      return arr

def merge(l, r):
   subarr = []
   lc = 0
   rc = 0
   # phase1: merge the arrays
   while lc < len(l) and rc < len(r):
      if l[lc] <= r[rc]:
         subarr.append(l[lc])
         lc += 1
      else:
         subarr.append(r[rc])
         rc += 1

   # phase2: copy remaining elements from l
   while lc < len(l):
      subarr.append(l[lc])
      lc += 1

   # phase3: copy remaining elements from r
   while rc < len(r):
      subarr.append(r[rc])
      rc += 1

   # return the merged array
   return subarr

a = [10, 5, 2, 20, -50, 30]
print(mergeSort(a))

Answer 2

Сначала вам нужно на самом деле return результат. Прямо сейчас вы ничего не возвращаете, поэтому получите None назад.

Во-вторых, просто присвойте той же переменной. left = mergeSort(left) и т. Д.

ОБНОВЛЕНИЕ:

Вот отлаженная версия.

a=[10,5,2,20,-50,30]

def mergeSort(arr):
    l=0
    h=len(arr)-1
    if h>l:
        mid=(l+h)//2
        left=arr[l:mid+1]
        right=arr[mid+1:]
        # Capture the merge into variables here.
        left=mergeSort(left)
        right=mergeSort(right)
        # Need a return of the merge.
        return merge(left,right)
    # Need to return arr if arr has 0 or 1 elements.
    else:
        return arr


def merge(l,r):
    subarr=[]
    lc=0
    rc=0
    loop=True
    while loop:
       if lc>len(l)-1 and rc<=len(r)-1:
          for i in range(rc,len(r)):
            subarr.append(r[i])
            loop=False
       elif lc<=len(l)-1 and rc>len(r)-1:
          for i in range(lc,len(l)):
            subarr.append(l[i])
            loop=False
       elif l[lc]<r[rc]:
          subarr.append(l[lc])
          lc+=1
          loop=True
       elif r[rc]<l[lc]:
          subarr.append(r[rc])
          rc+=1
          loop=True
       elif l[lc]==r[rc]:
          subarr.append(l[lc])
          subarr.append(r[rc])
          lc+=1
          rc+=1
          loop=True
    # Need to return the results of merge.
    return subarr

# Need to actually try calling the function to see the result.
print(mergeSort(a))

Я также отступил более разумно. Поверь мне, это важно.