Почему неправильно работает сортировка вставками из «Алгоритмов...» Кормена и др.?

Question

[aela_mate]

Вот псевдокод из книги:


Мой код на python:

for i in range(1,len(a)):
  key = a[i]
  j = i-1
  while j > 0 and a[j] > key:
    a[j+1] = a[j]
    j = j-1
  a[j+1] = key

Сортируется всё, кроме первого элемента. То есть было [5,2,4,6,1,3], стало [5, 1, 2, 3, 4, 6]. Почему так?

Comments

[Lynn «Кофеман»]

Вы специально поменяли i и j что бы читать неудобно было?

По сути, на картинке похоже массив нумеруется с 1, а у вас с 0. Так что ваше условие j > 0 неверное.

[aela_mate]

Вы специально поменяли i и j что бы читать неудобно было?

Простите...

Так что ваше условие j > 0 неверное.

Спасибо, действительно, с j>-1 нормально работает.

Answer 1

[Rsa97]

- while j > 0 and a[j] > key:
+ while j >= 0 and a[j] > key:

Answer 2

[Wataru]

Потому что в книге нумерация элементов идет с 1, а в питоне - с 0.

Надо поменять условия в циклах for и while.

Comments

[Lynn «Кофеман»]

В for вроде уже поменяно