Алгоритм сортировки слиянием выбрасывает "индекс списка из диапазона" для больших чисел

#python #list #algorithm #merge

#python #Список #алгоритм #слияние

Вопрос:

Прежде всего, я начну с того, что скажу, что в данный момент я изучаю python. Я пытаюсь понять сортировку слиянием, создавая программу самостоятельно. До сих пор я выполнял функцию, которая объединяет два списка. Проблема в том, что эта функция отлично работает для небольших чисел (например, 1-70 или что-то в этом роде), но если я захочу сойти с ума, выбрасывая число, подобное 100, это выдаст мне ошибку «индекс списка вне диапазона»

 def GenerateArray(n):
    randomlist=[]
    for i in range(0,n):
        n = random.randint(-100,100)
        randomlist.append(n)
    return randomlist

def Merge(a,b):
    c = list()
    i, j, k = 0, 0, 0
    longestList = max(len(a), len(b))
    if len(a) > len(b):
        while i < longestList:
            if a[i] == b[j]:
                c.append(a[i])
                i = i   1
                j = j   1
            elif j == len(b) - 1:
                i = i   1
                j = 0
            else:
                j = j   1
    else:
        while j <= longestList:
            if b[j] == a[i]:
                c.append(a[i])
                i = i   1
                j = j   1
            elif i == len(a) - 1:
                j = j   1
                i = 0
            else:
                i = i   1
    uniques = []
    for i in c:
        if i not in uniques:
            uniques.append(i)
    c = uniques
    print(c)


n=int(input("nHow many items would you like your first array to have? "))
a=GenerateArray(n)
print("The first array is: ")
print(a)
n=int(input("nHow many items would you like your second array to have? "))
b=GenerateArray(n)
print("The second array is: ")
print(b)
print("Merging the arrays...")
Merge(a,b)

1. Я получаю ту же ошибку даже при n = 10 . Это происходит потому, что вы увеличиваете и i то, и j другое, не проверяя, находятся ли они в допустимом диапазоне. Вместо увеличения, вы можете сделать i = max(i 1, len(a) - 1) и j = max(j 1, len(b) - 1)

2. Извините, похоже, я забыл что-то изменить в своем, пытаясь найти решение. В функции слияния для ветви IF первым условием является while i <= Самый длинный список: а в ветке else условием является while j < Самый длинный список: таким образом, он не будет выдавать ошибку для n = 10 или аналогичных значений.

3. while j < longestList по-прежнему не помогает вам решить проблему i len(a) - 1 увеличения. Аналогично, i < longestList не улавливает проблему j увеличения сверх допустимого предела.

4. Кроме того, похоже, что ваше решение сработало для меня, большое вам спасибо!

5. Пробовал больше комбинаций, и похоже, что я имею дело с той же ошибкой для комбинации n, n = 6,10

Ответ №1:

Разве вы не делаете это очень сложным способом? Насколько я понимаю, вы объединяете два списка, а затем распечатываете в них уникальные номера. Вы можете сделать это всего за несколько строк кода.

 c = a   b
unique = []
for i in c:
    if c.count(i) == 1:
        unique.append(i)
print(unique)

Прошу прощения, если я неправильно понял цель этой программы.

1. Вы абсолютно правы. Спасибо вам за этот комментарий, похоже, у меня действительно есть склонность к чрезмерному усложнению. Хорошего дня и еще раз спасибо!

2. Никаких проблем. Я желаю вам того же.