Сортировка вставки не работает - индекс списка вне диапазона

#python #python-2.7 #insertion-sort

#python #python-2.7 #вставка-сортировка

Вопрос:

Пытаюсь создать сортировку по вставке, но получаю сообщение об ошибке…

На самом деле не знаю, почему это происходит. Он всегда имеет тенденцию пропускать 37

 numbers = [45,56,37,79,46,18,90,81,50]

def insertionSort(items):
    Tsorted = []
    Tsorted.append(items[0])
    items.remove(items[0])
    for i in range(0,len(items)):
        print (Tsorted)
        if items[i] > Tsorted[len(Tsorted)-1]:
            Tsorted.append(items[i])
        else:
            Tsorted[len(Tsorted)-2] = items[i]
        items.remove(items[i])

insertionSort(numbers)

Ошибка:

     if items[i] > Tsorted[len(Tsorted)-1]:
IndexError: list index out of range

1. Это не связано с вашей ошибкой. Это уже объяснялось в ответах, но я хотел добавить, Tsorted.append(items.pop(items[0])) равно тому, что вы делаете в этих двух строках. Кроме того, Tsorted[-1] даст вам тот же результат, что и Tsorted[len(Tsorted)-1]

Ответ №1:

Первое: вы удаляете элементы из массива, которые вы повторяете внутри цикла здесь : items.remove(items[i]) . Как правило, это не очень хорошая идея.

Во-вторых: этот алгоритм не реализует сортировку по вставке, даже если вы исправите проблему с удалением. Вам следует ознакомиться с алгоритмом, например, здесь Сортировка вставки в Википедии. Для поиска правильного места вставки требуется еще один цикл.

В-третьих: в случае else вы перезаписываете вместо вставки значений.

Ответ №2:

Вы удаляете элементы из items цикла; таким образом, i может стать значением, которое было действительным индексом в оригинале items , но больше не находится в сокращенном.

Если вам нужно удалить элементы из items , похоже, вам следует подождать, пока цикл не будет завершен.

Ответ №3:

Это потому, что вы звоните tems.remove() . Ваш код завершается с ошибкой, когда i= 4 и items=[37, 46, 90, 50] .

Таким образом, у них уже нет элемента с индексом 4 , но с 3 поскольку индексация начинается с 0.

Ответ №4:

range(0,len(items) будет вычисляться только при первом попадании вашего кода в цикл for, в каком состоянии len(list) = 8 . Это означает, что вы будете выполнять итерацию

 for i in [0,1,2,3,4,5,6,7]
    #Do stuff...

Но в то же время вы удаляете элементы из своего списка в каждом цикле. Итак, при нажатии i = 4 вы повторили свой цикл 4 раза, а длина вашего item списка составляет всего 4, что означает, что items[4]
он больше не существует.