Алгоритм Python для сортировки вставками: почему мы вычитаем 1 из i?

Привет и добро пожаловать в SO,

range(a, b) в питоне эквивалентно [a, b[ в математике с a и b двумя плавающими числами и a < b

А range(b) эквивалентно [0, b[ в математике.

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

вероятно, эта гифка из викимедиа хорошо описывает это. если встроенный gif не работает, посмотрите ссылку: https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif

по этой причине вам нужно i = i -1 вернуться назад и поместить в нужное место.

Рассмотрим пример: arr = [12, 11, 13, 5, 6]

Массив виртуально разделен на отсортированную и несортированную части. Значения из несортированной части выбираются и помещаются в правильную позицию в отсортированной части.

Первый проход:

Начиная с первых двух элементов

   12          11          13          5       6   

Здесь 12 больше 11, следовательно, они не в порядке возрастания, а 12 не в правильном положении. Таким образом, поменяйте местами 11 и 12. Итак, на данный момент 11 хранится в отсортированном подмассиве.

Второй проход:

Теперь перейдите к следующим двум элементам и сравните их.

   11          12          13          5       6   

Здесь 13 больше, чем 12, поэтому оба элемента кажутся в порядке возрастания, следовательно, перестановки не произойдет. 12 также хранится в отсортированном подмассиве вместе с 11.

Третий проход:

Теперь переходим к следующим двум элементам: 13 и 5.

   11          12          13          5       6   

И 5, и 13 не находятся на своих местах, поэтому поменяйте их местами.

   11          12          5       13          6   

После замены элементы 12 и 5 не сортируются, поэтому снова меняем местами

   11          5       12          13          6   

Здесь снова 11 и 5 не отсортированы, поэтому снова меняем местами

   5       11          12          13          6   

здесь он находится на своем правильном месте

Затем мы повторяем тот же процесс в каждом проходе.

Вы можете видеть из примера, когда одна пара элементов находится в неправильном порядке, мы продолжаем менять их местами с индекса текущего элемента назад, пока они не будут в правильном порядке. поэтому мы устанавливаем i = i - 1 в коде алгоритма.

Without,i=i-1 соседние элементы проверяются один раз. так что в конце [2,3,5,7,4,1] станет [2,3,5,4,1,7] . Для этого (без i = i-1) вам нужно реализовать двойной цикл for, как показано ниже, и вы можете заменить while loop на if condition или оставить как есть.

def insertion_sort(list_a):
  indexing_length = range(1,len(list_a))
  #this is double for-loop
  for _ in indexing_length:
      for i in indexing_length:
        # print(i)
        value_to_sort = list_a[i]
        if list_a[i-1] > value_to_sort and i>0:
          list_a[i], list_a[i-1] = list_a[i-1], list_a[i]  
        print(list_a)
  
  return list_a

На самом деле описанный выше метод прост для понимания и используется везде, где мы дважды проверяем каждые два соседних элемента, Но чтобы уменьшить количество проверок сравнения, мы можем использовать цикл while с я = я-1.