Having an issue with an insertion sort algorithm python

Question

I am doing an assignment where we are given a text document with no greater than 10^6 numbers. Can be positive or negative. We are then tasked with creating a function that uses an insertion sort algorithm to sort the list up to a defined index which may or may not include the entire list. We then need it to output the sorted list and the number of times the algorithm moved items to sort (or how many times it had to iterate to sort the entire list.

I have it working just fine with a sample list just to sort it and then output the sort. this is how I did it.

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)

This works perfectly, the output I get is [1,2,3,4,5,5,6,9]. However, as soon as I add in my counter. it stops working. I basically just added a few lines in the function.

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)

which just prints out the same as before. So, I moved a few things around based on errors and wound up at:

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)

This gives me an error I'm not sure how to solve which is, local variable 'counter' is referenced before assignment.

So I gave up on that for a minute and ran into yet another problem. I wanted to just at least get it working extracting the data from the .txt and sorting it. So using the file I received I just changed the first 2 lines of the program and it gives me yet another error I am not sure how to fix.

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

there are close to 1000 items in this list. the error I receive here is;

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

I apologise for the wall of text, and probably asking a simple question, but I have been stuck on this for 2 days now, and have read at least 4 different articles around insertion sorts and still have gotten nowhere.

Answer 1

Okay just wanted to post the solution to this issue. Thank you to Dillon Davis, mortysporty.

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 2

There were a few issues. To resolve the index error, set n to be precisely the length of arr. Then, to fix the counter bug, move the counter back into the local scope (its declaration anyways). Lastly, you never unpack the counter and arr, so neither get updated.

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)

Notice also that I change how arr is read in:

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

and take the min of your target n and len(arr), to avoid indexing beyond the end of the array.

Answer 3

So, I tried doing a few of the solutions suggested and ended up with

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)

it just reprints out the list that was input, and the counter of 0

Answer 4

Your second function (the one you define in your second block of code) is fine… but you dont catch your return arguments properly. Do

sorted_arr, counter = insertionSort(arr, n)

to get the counter.