Constructive Insertion Sort

Question

I having trouble with insertion sort and I feel I might be missing the point of the sort and misunderstanding the fundamentals.

We were given a insertion sort which edited the array which was fed into it. We are tasked with then modifying the code we have been given to then create a constructive insertion sort which will not edit the original array

This is the code I have so far

def append(A, x):
    return A + [x] 

def insertionSort(A):
    B = []
    B = append(B, A[0])
    for i in range(1, len(A)):
        B = insert(B, A[i], i, A)
    return str(B)

def insert(B, k, hi, A):
    print(B, k, hi)
    for x in range(hi-1, -1, -1):
        if B[x] <= k:
            B = append(B, k)
            return B
        B = append(B, A[x])
    B[0] = k 
    return B

print(insertionSort([2,4,6,8,10,1,3,5,7,9]))

However after the third or forth element in the list it begins adding all the items to the end of the list in reverse order

[2] 4 1
[2, 4] 6 2
[2, 4, 6] 8 3
[2, 4, 6, 8] 10 4
[2, 4, 6, 8, 10] 1 5
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2] 3 6
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3] 5 7
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5] 7 8
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5, 7] 9 9
[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5, 7, 9]

I cannot wrap my head around why this is wrong.

Thanks dearly to anyone who can help.

Answer 1

The reverse problem is at the foor loop in the insert function when your loop hit those values it starts the reverse mode

def insert(B, k, hi, A):
    # when hi=5
    for x in range(hi-1, -1, -1):
        # x = 4
        # here B[4] is 10 and k=1 so B[4] <= 1 is False
        # you program does not execute the inside of if
        # instead it jumps to B = append(B, A[x]) where A[4] == 10
        # and the this loop goes in reverse mode from 4 to 0
        # when x = 3
        # B[x] = 8 so 8 is not less or equal of k where k = 1
        # so it jumps again to B = append(B, A[x]) where A[x] = A[3] = 8
        # so it append 8 
        # and so on 
        # when this loop is finished your list will look like [1,4,6,8,10,10,8,6,4,2]
        # the 1 gets added when the loop is finished at B[0] = k 
        # and then rest of the outputs are result of the loop inside the insertionSort func
        if B[x] <= k:
            B = append(B, k)
            return B
        B = append(B, A[x])
    B[0] = k 
    return B

Here is a solution:

def insertionSort(A):
    copy_sort = A.copy()

    for i in range(1, len(copy_sort)):
        item = copy_sort[i]

        j = i - 1
        while j >= 0 and copy_sort[j] > item:
            copy_sort[j + 1] = copy_sort[j]
            j -= 1
        copy_sort[j + 1] = item

    return copy_sort


your_array = [2,4,6,8,10,1,3,5,7,9]
sorted = insertionSort(your_array)
print(your_array)
print(sorted)

Answer 2

You need to work out your algorithm on paper, and then translate those steps to Python code. What you've implemented is convoluted and incorrect.

Most of all, insert is very confused as to the information it needs and how it should do its job. As best I can see from your code, you want this routine to insert a given value k into the appropriate location in list B. For some reason, you've also passed in list A and the value's location in that list, neither of which is applicable.

What your routine does then is strange; starting from the end of B (using i instead of B itself), the code checks the elements of B; every time it finds a value in the list less than the new one, it appends the new one to the end of B. Regardless of that comparison, it appends the corresponding element of A to B. Nowhere do you insert the element in the proper place.

Rewrite this code. Start with the minimum necessary information:

def insert(arr, new_val):
# insert new_val into the list arr

Now, your function has two steps to carry out:

• Find the proper position for new_val
• Make a new list with the value inserted into that spot.

You return that new list.

Can you move on from there?