Невозможно получить сортировку вставки из введения в алгоритмы 3-е изд. правильно. Где моя ошибка?

Я работаю над книгой "Введение в алгоритмы", 3-е издание. Одной из первых вещей объясняется сортировка вставки. На странице 18 есть некоторый псевдо-код:

A = {5, 2, 4, 6, 1, 3};

INSERTION-SORT(A)
1 for j = 2 to A.length
2   key = A[j]
4   i = j - 1

5   while (i > 0 and A[i] > key)
6     A[i + 1] = A[i]
7     i = i - 1

8   A[i + 1] = key

В нем говорится, что псевдокод используется так, что он легко переводится на любой язык (C, С++, Java, они не упоминаются, но я думаю, С# тоже). Поскольку я программирую на С#, я перевел его в LinqPad.

int[] a = { 5, 2, 4, 6, 1, 3 };

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

a.Dump();

Вероятно, вы спросите, почему я начинаю с 1, когда он ясно говорит 2? В книге массив имеет индекс, начинающийся с 1. И да, теперь я, вероятно, должен был обновить все [i - 1] и [i + i].

В любом случае, после того, как я закончил, я запустил код и заметил, что он действительно не сортируется правильно. Выходной сигнал { 5, 1, 2, 3, 4, 6 }. Было уже поздно и должно было остановиться, но я изо всех сил старался сделать код правильным. Я сделал все, даже взяв псевдокод, как из книги (начиная с 2). Все еще не правильный выход.

Я связался с одним из профессоров книги, и он пришлет мне код для сортировки вставки в C:

void insertion_sort(int *A, int n) {
  for (int j = 2; j <= n; j++) {
    int key = A[j];
    int i = j-1;

    while (i > 0 && A[i] > key) {
      A[i+1] = A[i];
      i--;
    }

    A[i+1] = key;
  }
}

Переведено на С#:

int [] a = {5, 2, 4, 6, 1, 3};

for (var j = 2; j <= a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

Я получаю массив за пределы. Тогда может быть:

int [] a = {5, 2, 4, 6, 1, 3};

for (var j = 2; j <= a.Length - 1; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

Выход: {5, 1, 2, 3, 4, 6}

Я думаю, это не может быть правильно. Псевдокод говорит 2 для array.Length. Это 2 < array.Length или 2 <= array.Length? Что здесь происходит?

Я лично считаю, что это из-за предиката 0 > 0 в цикле while. Он на самом деле падает каждый раз каждый раз.

Мое объяснение (от моего письма, отправленного профессору, ленив, чтобы набрать его):

Причина, по которой цикл все еще заканчивается { 5, 1, 2, 3, 4, 6 }, обусловлен предикатом i > 0. Каждый раз в цикле while вычитаете 1 из я (i--). Это в конечном итоге приведет к 0 > 0, который заканчивается ложным (только 0 == 0 вернет true), но это происходит, когда цикл еще нужно запустить еще раз. Он непрерывно падает на один короткий. Для правильного сортировки нужно сделать цикл while еще 1 раз.

Другое объяснение:

Когда j начинается с 2, ключ == 4, я == 1 и [i] == 2. В этом случае цикл while не будет работать, потому что 2 > 0, но 2 не больше 4.

j == 3, key == 6, i == 2, a[i] == 4

Пока цикл не будет запущен, потому что 4 не больше 6

j == 4, key == 1, i == 3, a[i] == 6

Пока цикл работает на ходу:

a[i + 1] = a[i] -> a[4] = a[3] -> { 5, 2, 4, 6, 6, 3 } i-- -> i == 2

Опять цикл while, потому что 2 > 0 и 4 > 1

a[i + 1] = a[i] -> a[3] = a[2] -> { 5, 2, 4, 4, 6, 3 } i-- -> i == 1

Опять цикл while, потому что 1 > 0 и 2 > 1

a[i + 1] = a[i] -> a[2] = a[1] -> { 5, 2, 2, 4, 6, 3 } i-- -> i == 0

И вот где это происходит (на мой взгляд) неправильно. я теперь равен нулю, но цикл while должен запускаться еще раз, чтобы получить 5 из нулевой позиции.

Профессор уверяет меня, что он прав, но я не могу получить правильный результат. Где мое мышление идет не так?

Массив в коде C, который был отправлен мне профессором, фактически начинался с индекса 1. Я не знал этого и проверял массивы C, я видел, что все они начинаются с 0. Да, тогда C код не дает правильного вывода. Профессор объяснил это мне, и теперь фигуры теперь попадают на его место.

Ответы

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i >= 0 && a[i] > key)  <----------- Try this, or you'd miss the first number
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

int a[] = {5,2,4,3,1};
    int key;
    int i;
    for(int j = 0; j < 5; j++)
    {
        key = a[j];
        i = j - 1;

        while(i>=0 && a[i]>key)
        {
            a[i+1]= a[i];
            i--;
        }
        a[i+1] = key;

        for(int k=0; k<a.length;k++)
        {
            System.out.print(a[k]+" ");
        }
    }

#include <stdio.h>

int main(void)
{
  int A[] = { 50, 20, 10, 40, 60, 30 };
  int j, key, len, i;
  len = (sizeof(A)) / (sizeof(A[0]));

    for (j = 1; j < 6; j++) {  <-- Change here
      key = A[j];
      // Insert key into the sorted sequence A[1 .. j - 1].
      i = j - 1;
      while (i >= 0 && A[i] > key) {  <-- Change here
          A[i + 1] = A[i];
          i--;
      }
      A[i + 1] = key;
    }

    for (int z = 0; z < len; z++) {
       printf("%d ", A[z]);
    }
   printf("\n");
 }

largo = length
actual = current
cadena = chain

void InsertionSort::Sort(char cadena[])
{
    int largo = strlen(cadena) - 1;
    char actual = '0';
    int i = 0;

    for (int j = 1; j <= largo; j++)
    {
        actual = cadena[j];
        i = j - 1;
        while(i >= 0 && cadena[i] > actual)
        {
            cadena[i + 1] = cadena[i];
            i--;
        }
        cadena[i + 1] = actual;
    }
}