Ошибки возникают при реализации сортировки слиянием в Python

Question

Я пытаюсь реализовать сортировку слиянием в python следующим образом:

def MergeSortTopdown(list_n):
     #Base condition to stop recursion
    if len(list_n) == 1:
        return list_n
    else:
        mid = int(len(list_n)/2)
        first_half = list_n[:mid]
        second_half = list_n[mid:]
        MergeSortTopdown(first_half)
        MergeSortTopdown(second_half)
        i = 0
        j = 0 
        n = len(list_n)
        for k in range(n):
            if j >= len(first_half) and i < len(second_half):
                list_n[k] = first_half[i]
                i += 1 
            if i >= len(first_half) and j < len(second_half): 
                list_n[k] = second_half[j]
                j += 1
            if i < len(first_half) and j < len(second_half):
                if first_half[i] > second_half[j]:
                    list_n[k] = second_half[j]
                    j += 1   
                elif second_half[j] > first_half[i]:
                    list_n[k] = first_half[i]
                    i += 1
                elif second_half[i] == first_half[j]:
                    list_n[k] = first_half[i]
                    if i>j:
                        i += 1
                    else:
                        j += 1

    return list_n

кажется разумным, когда я тестировал уже отсортированный список. Однако, когда я бегу, эта ошибка возникает:

MergeSortTopdown([3,4,6,7,1,8,56,112,67])
Traceback (most recent call last):

  File "<ipython-input-11-29db640f4fc6>", line 1, in <module>
    MergeSortTopdown([3,4,6,7,1,8,56,112,67])

  File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown
    MergeSortTopdown(second_half)

  File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 13, in MergeSortTopdown
    MergeSortTopdown(second_half)

  File "C:/Users/Emmanuel Hoang/MergeSortTopDown.py", line 19, in MergeSortTopdown
    list_n[k] = first_half[i]

IndexError: list index out of range

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

Answer 1

Вы пытались сослаться на элемент после конца списка. Я добавил несколько простых print утверждений в ваш код:

   for k in range(n):
        print("LOOP TOP", k, first_half, second_half, list_n)
        if j >= len(first_half) and i < len(second_half):
            print("TRACE", list_n, k, "\t", first_half, i)
            list_n[k] = first_half[i]
            i += 1

Затем я сократил список ввода до [8,56,112,3,67].

Выход:

LOOP TOP 0 [8] [56] [8, 56]
LOOP TOP 1 [8] [56] [8, 56]
LOOP TOP 0 [3] [67] [3, 67]
LOOP TOP 1 [3] [67] [3, 67]
LOOP TOP 0 [112] [3, 67] [112, 3, 67]
LOOP TOP 1 [112] [3, 67] [3, 3, 67]
TRACE [3, 3, 67] 1   [112] 0
LOOP TOP 2 [112] [3, 67] [3, 67, 67]
TRACE [3, 67, 67] 2      [112] 1

За этим следует крушение, которое вы получили. Вы пытаетесь получить first_half[1], когда есть только элемент 0.

АНАЛИЗ

У вас есть три последовательных if оператора для проверки границ списка:

        if j >= len(first_half) and i < len(second_half):
        if i >= len(first_half) and j < len(second_half): 
        if i < len(first_half) and j < len(second_half):

Вы включили i и j при первой проверке: i - индекс first_half. Это изменение исправляет слияние:

        if i < len(first_half) and j >= len(second_half):

Предложения

Часть вашей проблемы в том, что ваша логика слияния слишком сложна. У вас есть единственная проверка значения во время основной части цикла: переместите нижнюю часть заголовков списка в объединенный список. Делайте это, пока оба индекса находятся в диапазоне.

Затем, когда один индекс достигнет конца своего списка, выпадет из цикла и добавит остальные элементы другого списка. Используйте метод extend. Итак ...

while i < len(first_half) and j < len(second_half):
    if first_half[i] < second_half[j]:
        # move smaller element to list_n;
        # increment i or j as needed
    k += 1

# One of these will be an empty operation.
list_n.extend(first_half[i:])
list_n.extend(second_half[j:])

Answer 2

Для разрешения IndexError:

Первый случай, который вы проверяете в своем «шаге слияния» сортировки слиянием - если вы уже объединили все элементы из списка second_half - содержит имена ваших двух списков first_half и second_half переключился Вместо этого:

if j >= len(first_half) and i < len(second_half):
    list_n[k] = first_half[i]
    i += 1 

у вас должно быть это:

if j >= len(second_half) and i < len(first_half):
    list_n[k] = first_half[i]
    i += 1

Это правильно проверит состояние, указанное выше.

Почему это происходило:

Причина, по которой вы получили IndexError, заключается в том, что вы пытались позвонить first_half[i] и неправильно подтвердили, что i был допустимым индексом в списке first_half, прежде чем это сделать.