Конструктивная сортировка вставок

Question

У меня проблемы с сортировкой вставок, и я чувствую, что, возможно, упускаю точку сортировки и неправильно понимаю основы.

Нам дали сортировку вставок, которая редактировала массив, который был введен в нее. Перед нами стоит задача изменить код, который нам дали, чтобы затем создать конструктивную сортировку вставки, которая не будет редактировать исходный массив

Это код, который у меня есть до сих пор

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]))

Однакопосле третьего или четвертого элемента в списке он начинает добавлять все элементы в конец списка в обратном порядке

[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]

Я не могу понять, почему это не так.

Спасибо всем, кто может помочь.

Answer 1

Обратная проблема в цикле foor в функции вставки, когда ваш цикл достигает этих значений, он запускает обратный режим

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

Вот решение:

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

Вам нужно разработать свой алгоритм на бумаге, а затем перевести эти шаги в код Python. То, что вы реализовали, запутано и неправильно.

Больше всего insert очень запутано в отношении информации, которая ему нужна, и того, как она должна выполнять свою работу. Как я могу видеть из вашего кода, вы хотите, чтобы эта подпрограмма вставляла данное значение k в соответствующее место в списке B. По какой-то причине вы также передали список A и расположение значения в этом списке, ни одно из которых не применимо.

То, что делает ваша подпрограмма, тогда странно;начиная с конца B (используя i вместо B), код проверяет элементы B;каждый раз, когда он находит значение в списке меньше нового, оно добавляет новое в конец B. Независимо от этого сравнения, он добавляет соответствующий элемент от A к B. Нигде вы не вставляете элемент в нужное место.

Перепишите этот код. Начните с минимально необходимой информации:

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

Теперь ваша функция должна выполнить два шага:

• Найти правильную позицию для new_val
• Создайте новый список со значением, вставленным в это место.

Вы вернете этот новый список.

Можете ли вы идти дальше?