Сортировка вставок из T Cormen Book

Question

Я работаю над книгой Кормена «Введение в алгоритмы» и создал следующее из псевдокода.Однако первые два элемента массива, похоже, не отсортированы.Я не могу определить ошибку (возможно, потому что уже поздно).Поэтому мне было интересно, если кто-нибудь мог видеть с первого взгляда.

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(){
  int input;
  cout << "Enter length of desired array." << "\n";
  cin >> input;
  cout << "\n";

  int A [input];

  //Populate and print the Array.
  for(int i=0; i<input; i++){
    A[i] = rand()%99-1;
    cout << A[i] << " ";
  }

  cout << "\n";

  //Insertion sort.
  for(int j=2; j<input; j++){ //Iterate through the Array.
    int key = A[j]; //Store the current element into key.
    int i = j-1; //Iterator for while loop.
    while(i>0 && A[i]>key){ //Loop to insert A[j] into the sorted sequence.
      A[i+1] = A[i]; //Move the element.
      i=i-1; //New value of i.
      A[i+1] = key; //Update the key
    }
  }

  for(int i=0; i<input; i++){
    cout << A[i] << " ";
  }
  return 0;
}

Answer 1

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

Главный подозреваемый

for(int j=2; j<input; j++)

Где вы можете начать с 1 вместо 2.

Условие прекращения

while(i>0 && A[i]>key)

также необходимо изменить, чтобы убедиться, что вы выше -1, а не 0.

EDIT:

После чуть более пристального взгляда я почти уверен, что do также необходимо отрегулировать while.

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

Answer 2

изменить на for (int j = 1; ...)

Answer 3

На самом деле ваш код верен, но проблема заключается в инициализации цикла for.псевдокод для вставки сортировки:

for j ←1 to length(A)-1
 key ← A[ j ]
 > A[ j ] is added in the sorted sequence A[0, .. j-1]
 i ← j - 1
 while i >= 0 and A [ i ] > key
     A[ i +1 ] ← A[ i ]
     i ← i -1
 A [i +1] ← key

На самом деле ваш код не учитывает первый элемент массива.Это просто начало сортировки со второго элемента массива, в котором вы получаете такой тип результата.

Просто измените инициализацию j на 1, и она будет работать правильно.

Answer 4

Взгляните на алгоритм сортировки вставки CLRS, переведенный на 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;

        System.out.println("i in for loop "+i);

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

Answer 5

Вы можете использовать этот код, я исправил вашу ошибку

#include<iostream>
#include<stdlib.h>
#include<cstdlib>

using namespace std;

int main(){
    int input;

    cout<< "Enter length of desired array";
    cin>>input;

    cout<<"\n";

    int A[input];

    for(int i = 0 ;i <input ; i++)
    {
        A[i] = rand() % 100;   
        cout<<A[i] << "\t";
    }

    cout<<"\n";

    for(int j =1; j<input ; j++)
    {   int i;
        int 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(int i = 0 ;i <input ; i++)
    {
        cout<<A[i] << "\t";
    }
}