Why is Insertion_Sort duplicating numbers within a list instead of sorting it?

Question

I was trying to implement an Insertion Sort code using a sample code provided using a lecture, and despite placing the code word for word, the Insertion Sort function does not sort an array by ascending order. The code instead gives a duplicate number, say 2 within the array.

I've tried to adjust the end value for the range function from n-1 to n, but all it does is give me 2 arrays, both arrays with at least 1 number duplicated. Changing the position of array[j] and array[j - 1] under the while loop only changes the duplicate numbers from 2 to 3.

Nothing seems to sort the array to give the answer [1,2,3] and I have no idea what exactly is wrong with this code, so why is Insertion Sort giving me duplicates instead of properly sorting the array?

The code below is what I was using.

def function insertion_sort(array):
    
    n = len(array)
    
    for i in range(1, n-1): 
        j = i #j is inner index, i is inner index
        temporary = array[j]
       
        
        while (j > 0) and (array[j] < array[j-1]):
            array[j]= array[j - 1]#shift right
            j = j - 1 #move left 
            print(array)
            
        array[j] = temporary #save to final position

array = [3,2,1] #test case
insertion_sort(array)

Result when n-1 is changed to n:

[3, 3, 1] #3 is duplicated, 2 has disappeared

Result when position of array is swapped:

[2, 2, 1] #2 is duplicated, 3 has disappeared

Answer 1

I think your code is valid. But note that currently your implementation sorts number in a descending order due to this comparison: array[j] < array[j-1] It should be reverted to have it sort arrays in a ascending order.

Your problem is with with understanding what your code does. You talk about what it gives you, but actually your functions 'gives' you nothing. You only have an intermediate result printed out (just before the assignement of the temporary value back, this is why you think you get duplicates). You should rather displace this print() after all processing or have your function return something.

Try using various test cases to pin out what might be a problem in your code. I think also since you are learning that you don't fully grasp what the code is doing. Try reading a bit about algorithmics and python.

Answer 2

As you were able to run the code, I suppose the function word is a mistake in your post here only -- it shouldn't be there.

Besides that, there are these issues:

• The comparison array[j] < array[j-1] will be false as soon as j gets into the already sorted part of the array, which will prevent the inner loop from making a second iteration. What you really want here is to compare temporary < array[j-1]. With that fix your function will sort the array in ascending order.

• range(1, n-1) prevents the loop from moving the last value to its sorted position. The range currently excludes n-1 (that's how range works). This should be corrected to range(1, n).

• You seem to expect that the result of the sort operation is printed, but this is not true. You have a print statement somewhere in the middle of the shifting process, which gives a wrong impression about duplicates. On the other hand your code does not show the final result of the function call. You should place a print(array) after the call of insertion_sort(array). Then you will not see duplicates.

Some other remarks:

• A comment that says "j is inner index, i is inner index" is not clarifying anything useful.

• Also, it is not needed to put parentheses around the compare operators.

Here is your code with that those fixes applied to it:

def insertion_sort(array):
    n = len(array)
    
    for i in range(1, n):
        j = i 
        temporary = array[j]
        while j > 0 and temporary < array[j - 1]:
            array[j] = array[j - 1]  # shift right
            j = j - 1  # move left             
        array[j] = temporary  # save to final position

array = [3,2,1]  # test case
insertion_sort(array)
print(array)  # 1 2 3

More Pythonic

• In a Python loop it is not common to update loop variables with something like j = j - 1. The inner loop could be rewritten in a more Pythonic way.
• When iterating over an array where you also need the index you can benefit from using the enumerate function.
• The shift-right operations could be delayed until after the inner loop. At that time you can shift several adjacent items to the right in one move using slicing syntax.

For instance:

def insertion_sort(array):
    for i, value in enumerate(array):
        for j, other in enumerate(array):
            if other >= value:
                break  # guaranteed to occur
        # Move value back to index j, shifting the intermediate slice to the right
        array[j:i+1] = value, *array[j:i]

And if we turn the inner loop into a next() comprehension, then:

def insertion_sort(array):
    for i, value in enumerate(array):
        j = next(j for j, other in enumerate(array) if other >= value)
        array[j:i+1] = value, *array[j:i]