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

Question

Я работаю над книгой «Введение в алгоритмы», 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, C ++, Java, они не упоминают, но я думаю, что и C # тоже). Поскольку я программирую на C #, я перевел его на 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();

Вы, вероятно, спросите, почему j начинается с 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;
  }
}

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

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 к массиву. Длина. Это 2

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

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

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

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

Когда j начинается с 2, key == 4, i == 1 и a [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 код не дает правильный вывод. Профессор объяснил мне это, и теперь все стало на свои места.

Answer 1

Я думаю, что prof использует нотацию массива на основе 1, поэтому при while (i > 0 && a[i] > key) в цикле отсутствует элемент a [0].Измените свой исходный код на этот, тогда он будет работать:

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;
}

Кроме того, если вы хотите использовать код профессора, просто проигнорируйте там 0-й элемент.

На примечании стороны,с кем ты связался?Ривест?Корман?В следующий раз, когда я запутался, я думаю, что я тоже попытаюсь связаться с ним, так как кажется, что этот профессор отвечает на письма:)

Answer 2

Вы должны думать не о переводе псевдокода, а о переводя ваше понимание алгоритма.

Сначала массив полностью не отсортирован. Алгоритм работает по брать последовательные несортированные элементы и вставлять их в уже отсортированная часть. Начальная «отсортированная часть» является первым элементом, который тривиально "отсортирован". Итак, первый элемент для вставки второй. Какой индекс второго элемента? Ваш j должен начать с этого.

Затем i должен пройти через все индексы отсортированных элементов, назад, пока он не найдет место для вставки текущего значения или заканчивается элементов. Итак, где это должно начаться, и где это должно закончиться? Позаботьтесь о том, чтобы он действительно смотрел на каждый элемент это должен.

Одиночные ошибки, как известно, трудно обнаружить (и смешивать понятия массивов на основе 1 и 0, безусловно, не помогают), но не просто возиться, пока это не сработает. Попытайтесь понять, что код на самом деле делает.

Answer 3

У меня возникла такая же проблема. Ниже приведен код на C, который правильно реализует приведенный выше псевдокод. Я не использую указатели, как другие решения.

Действительно, хитроумно было то, что псевдокод использует нотации массива на основе 1 в отличие от большинства языков программирования!

#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");
 }

Answer 4

Я тоже сталкивался с вашей проблемой и нашел решение этой проблемы.Я кодировал алгоритм в Java, как показано ниже.

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]+" ");
        }
    }

Answer 5

Я считаю, что ваш аргумент о i>0 является верным, независимо от того, что проф. говорит. В псевдокоде цикл равен while i > 0, а индексация массива начинается с 1. В C # индексация массива начинается с 0, поэтому вы должны иметь while i >= 0.

Answer 6

Помните: A.length идет от 0 до n, поэтому длина должна быть A.Length -1. Я сделал этот алгоритм для моих студентов на C ++ на испанском языке, используя эту книгу. Прост в переводе на C #.

перевод, чтобы вы могли лучше понять

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;
    }
}