Я неправильно интерпретирую этот псевдокод?

Question

Я неправильно интерпретирую этот псевдокод?

У меня есть этот псевдокод:

COMPARE-EXCHANGE(A,i,j)
if A[i] > A[j]
exchange A[i] with A[j]

INSERTION-SORT(A)
for j = 2 to A.length
for i = j-1 downto 1
COMPARE-EXCHANGE(A,i,i+1)

Я бы интерпретировал это как:

void insertSort( )
{
int tmp;

for( int j = 2 ; j < MAX ; ++j )
{
for( int i = j - 1 ; i > 0 ; --i )
{
if( unsortedArr[i] > unsortedArr[i + 1] )
{
tmp                 = unsortedArr[i];
unsortedArr[i]      = unsortedArr[i + 1];
unsortedArr[i + 1]  = tmp;
}
}
}
}

Однако это будет пропустить unsortedArr[0],
Что означает, что это не сработает.

Изменение 2-го for чтобы:

for( int i = j - 1 ; i >= 0 ; --i )

Заставит его работать как задумано.
Ошибка в псевдокоде или моя первая попытка неверной интерпретации?

2

algorithm array-algorithms c++

Решение

Другие решения

Я думаю, что ваш псевдокод предполагает, что массивы начинаются с индекса один [1] — где в C & C ++ они начинаются с нуля [0].

3

Я предполагаю, что псевдокод использует индексацию на основе 1, а не индексацию на основе 0, которую использует C ++.

2

Источник

Accepted Answer

Однако это пропустит unsortedArr [0]. Что означает, что это не сработает.

Псевдокод почти универсален для нумерации элементов массива от 1, а не от нуля, как в C / C ++

Изменение 2-го на:

для (int i = j — 1; i> = 0; —i)

Заставит его работать как задумано.

Этого недостаточно: вам также нужно начать j в 1 скорее, чем 2 во внешней петле.

Также обратите внимание, что стандартная библиотека C ++ предлагает std::swap функция, которая позаботится о замене элементов массива за вас:

if( unsortedArr[i] > unsortedArr[i + 1] )
{
std::swap(unsortedArr[i], unsortedArr[i+1]);
}

4