Вставка внедрения (Ошибка), Python

Question

У меня есть две версии реализации INSERTION SORT; Я думаю, , которые эквивалентны, но второй возвращает неправильный отсортированный список. Это первый один:

def insertionSort(A): 
for j in range(1,len(A)): 

    key = A[j] 
    i = j 

    while i>0 and A[i-1]>key: 
     A[i] = A[i-1] 
     i -= 1 

    A[i] = key 

это второй один:

def insertionSort(A): 
    for j in range(1,len(A)): 

     key = A[j] 
     i = j-1 

     while i>0 and A[i]>key: 
      A[i+1] = A[i] 
      i -= 1 

     A[i+1] = key 

Я проверил эти два алгоритма с этим C массива

C = [54,26,93,17,77,31,44,55,20] 
insertionSort(C) 
print(C) 

В первом случае мой массив правильно отсортирован; во втором случае мой результат:

[54, 17, 20, 26, 31, 44, 55, 77, 93]

Второй случай происходит от псевдокода на моей школе книга. Почему он не работает правильно?

Answer 1

Вот исправление вашего второго кода:

def insertionSort(A): 
    for j in range(1,len(A)): 

     key = A[j] 
     i = j-1 

     while i>=0 and A[i]>key: 
      A[i+1] = A[i] 
      i -= 1 

     A[i+1] = key 

Разница заключается в >= направлении > в то время цикла. Чтобы понять, давайте обратимся к поведению сортировки вставки. Этот алгоритм сортировки предполагает, что массив [0, j-1] сортируется, а затем помещает элемент в нужное место.

Теперь давайте предположим, что мы wan't сортировать [4,3,2,0,5,6,7] и мы сейчас в таком состоянии:

A = [2, 3, 4, 0, 5,6,7] 

Первые три элемента находятся в нужном месте, и мы должны поставить 0 в своем праве позиция (индекс 0). От i = 2 до i = 0 условие A[i] > key всегда верно. Итак, мы будем делать: A [3] = A [2], A [2] = A [1], A [1] = A [0].

Затем мы выйдем из цикла с i = -1 и установите A[i+1] = A[0] = 0.

В вашей предыдущей версии цикл остановится на i = 0, и последняя инструкция будет делать A[0+1] = A[1] = 0. Поэтому, когда вы даете [2, 3, 4, 0, 5,6,7] в алгоритме, это дает плохой результат.