Возникла проблема с алгоритмом сортировки вставки Python

Question

Я выполняю задание, в котором нам дается текстовый документ не более 10 ^ 6 цифр.Может быть положительным или отрицательным.Затем нам поручено создать функцию, которая использует алгоритм сортировки вставками для сортировки списка до определенного индекса, который может включать или не включать весь список.Затем нам нужно, чтобы он вывел отсортированный список и сколько раз алгоритм перемещал элементы для сортировки (или сколько раз ему приходилось выполнять итерацию для сортировки всего списка.

У меня все отлично работает с образцомперечислите только, чтобы отсортировать, а затем вывести сортировку. Вот как я это сделал.

arr = [1,9,6,5,4,3,5,2]
n = 8

def insertionSort(arr, n):
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

insertionSort(arr, n)

print(arr)

Это работает отлично, вывод я получаю [1,2,3,4,5,5,6,9]. Однако, как только я добавляю в свой счетчикон перестает работать. Я просто добавил несколько строк в функцию.

def insertionSort(arr, n):
    counter = 0
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            counter += 1
        arr[j+1] = key
    return arr, counter
    print(counter)

insertionSort(arr, n)

print(arr)

, которая просто печатает то же самое, что и раньше. Итак, я переместил несколько вещей, основываясь на ошибках, и нашел:

arr = [1,9,6,5,4,3,5,2] #[open("rosalind_ins.txt").read().split(' ')]
n = 8
counter = 0

def insertionSort(arr, n):
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            counter += 1
        arr[j+1] = key
    return arr, counter

insertionSort(arr, n)
print(counter)
print(arr)

Это дает мне ошибку, я не знаю, как ее решить, local variable 'counter' is referenced before assignment.

Так что я на минуту отказался от этого и столкнулся с еще одной проблемой.Я хотел, по крайней мере, заставить его работать, извлекая данные из .txt и сортируя их. Поэтому, используя полученный файл, я просто изменил первые 2 строки программы, и это дает мне еще одну ошибку, которую я не уверен, как исправить.

arr = [open("rosalind_ins.txt").read().split(' ')]
n = 811

В этом списке содержится около 1000 наименованийя получаю здесь ошибку:

File "insertionSort.py", line 17, in insertionSort
    key = arr[i]
IndexError: list index out of range

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

Answer 1

Было несколько проблем. Чтобы устранить ошибку индекса, установите n равной длине arr. Затем, чтобы исправить ошибку счетчика, переместите счетчик обратно в локальную область (в любом случае его объявление). Наконец, вы никогда не распаковываете счетчик и arr, поэтому не обновляйтесь.

arr = [1,9,6,5,4,3,5,2] #arr = open("rosalind_ins.txt").read().split(' ')
n = min(8, len(arr))
counter = 0

def insertionSort(arr, n):
    counter = 0
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            counter += 1
        arr[j+1] = key
    return arr, counter

arr, counter = insertionSort(arr, n)
print(counter)
print(arr)

Обратите внимание также, что я изменяю, как arr читается в:

arr = open("rosalind_ins.txt").read().split(' ')

и возьмите минимум вашей цели n и len(arr), чтобы избежать индексации за концом массива.

Answer 2

Ваша вторая функция (та, которую вы определили во втором блоке кода) в порядке ... но вы не уловили возвращаемые аргументы должным образом. У

sorted_arr, counter = insertionSort(arr, n)

чтобы получить counter.

Answer 3

Хорошо, просто хотел опубликовать решение этой проблемы.Спасибо Диллону Дэвису, смертный.

arr = open("rosalind_ins.txt").read().split(' ')
n = 811
counter = 0

def insertionSort(arr, n):
    counter = 0
    arr = [int(i) for i in arr if isinstance(i, str)]
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            counter = counter + 1
        arr[j+1] = key
    return arr, counter

arr, counter = insertionSort(arr, n)
print(counter)
print(arr)

Answer 4

Итак, я попробовал сделать несколько предложенных решений и в итоге получил

arr = [open("rosalind_ins.txt").read().split(' ')]
n = len(arr)
counter = 0

def insertionSort(arr, n):
    counter = 0
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            counter = counter + 1
        arr[j+1] = key
    return arr, counter

sorted_arr, counter = insertionSort(arr, n)
print(counter)
print(sorted_arr)

он просто перепечатывает список, который был введен, и счетчик 0