Почему не работает алгоритм сортировки вставкой на c++?

Question

[MrChen]

Всем привет! Я начал читать Кормена Алгоритмы. Первый алгоритм, который я решил попробовать реализовать, это сортировка вставками.... Вот псевдокод:

Вот код, который я написал на c++:

#include <iostream>

using namespace std;

int main() {
	int m[6] = {5, 2, 4, 6, 1, 3};
	int key = 0;
	int i = 0;

	int length = sizeof(m) / sizeof(int);

	for(int j = 2; j <= length; j++) {
		key = m[j];

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

		m[i + 1] = key;
	}
}

Но он почему то не сортирует массив. Подскажите, почему?

Answer 1

[Антон Жилин]

Индексация с Си начинается с 0, а не с 1, как во многих примерах реализации алгоритмов. Соответственно, если видим A[t], то в Си это переносим, как A[t-1]

Comments

[MrChen]

Т.е везде, где m[j] мне нужно писать m[j - 1]?

[Антон Жилин]

Т.е. вот так

#include <iostream>

using namespace std;

int main() {
  int m[6] = {5, 2, 4, 6, 1, 3};
  int key = 0;
  int i = 0;

  int length = sizeof(m) / sizeof(int);

  for(int j = 2; j <= length; j++) {
    key = m[j-1];

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

    m[i + 1-1] = key;
  }
}

[MrChen]

Антон Жилин: я вывожу элементы массива такой конструкцией:

for(int a = 0; a <= length; a++) {
		cout << m[a] << "\n";
	}

И он показывает примерно вот такое:

3
3
3
3
3
3
-858993460

[Антон Жилин]

MrChen: Выход за границы массива. Допустимые индексы идут от 0 до 5 (всего 6 элементов), а на последней итерации вы печатаете m[6] ("седьмой" элемент), что совершенно недопустимо.

[Антон Жилин]

MrChen А сортировка не работает из-за ошибки в условии while, сверьтесь с алгоритмом.

[MrChen]

Антон Жилин: не очень понимаю.... В чем ошибка то?

[Антон Жилин]

MrChen: В алгоритме A[i] > key, у вас m[j] > 0

[MrChen]

Антон Жилин: Простите, я , слепой видимо. Все исправил, все работает!) Спасибо!)

[Антон Жилин]

MrChen: Не забываем отметить как решение)

Answer 2

[Олег Филимоненко]

Сильно надеюсь, что мой пример кому-нибудь поможет. Тот же учебник, та же задача. Пример на языке Си. Если есть ошибки или кто-то может дать рекомендацию по оптимизации алгоритма - жду комментариев.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i;
    int j;
    int key;
    int n;
    printf("Enter N; N - the size of Array\n");
    scanf("%d", &n);
    int A[n];

    for(i=0; i<=n-1; i++){
        printf("Enter A[%d] = ",i);
        scanf("%d", &A[i]);
    }
    for(j=1; j<=n-1; ++j){
        key = A[j];
        i=j-1;

        while(i>=0 && A[i]>key){
            A[i+1]=A[i];
            i=i-1;
        }
    A[i+1]=key;
    }
    for(i=0; i<=n-1; i++){
        printf("%d\ ", A[i]);

}
return 0;
}

Comments

[Олег Филимоненко]

Кстати, если кому-то понадобится, распишу с полными комментариями каждую строку.