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.

counter is defined in the global scope, but without the global keyword in the function, it thinks counter += 1 is incrementing a local counter, of which none have been declared. — Dillon Davis
– Dillon Davis, Commented Mar 12, 2019 at 18:57
Move counter = 0 inside the function, or put global counter at the top of the function. Preferably the former if possible. — Dillon Davis
– Dillon Davis, Commented Mar 12, 2019 at 18:57
In the first version withe the counter, you return the sorted array and the counter and then try to print out the counter: execution will never reach that print(counter). Also, the function returns two things, but when you call it you throw them both away. — NickD
– NickD, Commented Mar 12, 2019 at 19:03
regarding your second problem... what does arr look like after arr = [open("rosalind_ins.txt").read().split(' ')]. Sounds to me like it isnt read in properly. — mortysporty
– mortysporty, Commented Mar 12, 2019 at 19:25

mortysporty · Accepted Answer · 2019-03-12 19:15:16Z

1

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.

edited Mar 12, 2019 at 19:15

answered Mar 12, 2019 at 19:00

mortysporty

2,9118 gold badges36 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Brett Plemons Over a year ago

So as part of the assignment, we are just supposed to sort the list to a specified index 'n' so we will be given a value for n. which is why it is defined in my program.

mortysporty Over a year ago

i see :) disregard that part then. I will edit my answer.

Brett Plemons Over a year ago

i know this is probably a stupid question, but dont we need to define the innerSort function before calling it?

mortysporty Over a year ago

To answer your question (read to quickly) no... the order of definition does not matter. But I was wrong. You do not have to define the inner function. Your function is fine as it is.

Dillon Davis · Accepted Answer · 2019-03-12 19:33:44Z

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.

Brett Plemons · Accepted Answer · 2019-03-12 19:16:35Z

0

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

answered Mar 12, 2019 at 19:16

Brett Plemons

659 bronze badges

3 Comments

Dillon Davis Over a year ago

What does len(arr) print?

Dillon Davis Over a year ago

Bet its 1. I think you're wrapping your entire list in another list, so your sorting a list of lists with only one element. You need arr = open("rosalind_ins.txt").read().split(' '), no extra []

Dillon Davis Over a year ago

Updated my answer to reflect these fixes

Brett Plemons · Accepted Answer · 2019-03-16 15:17:17Z

0

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)

edited Mar 16, 2019 at 15:17

answered Mar 12, 2019 at 21:08

Brett Plemons

659 bronze badges

Collectives™ on Stack Overflow

Having an issue with an insertion sort algorithm python

4 Answers 4

4 Comments

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related