2

私はこの擬似コードを持っています:

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 )

意図したとおりに実行します。疑似コードに誤りがあるのでしょうか、それとも私の最初の解釈の試みが間違っていたのでしょうか?

4

3 に答える 3

4

ただし、それは unsortedArr[0] をスキップします。つまり、機能しません。

C/C++ のように、0 からではなく 1 から配列要素に番号を付ける疑似コードは、ほぼ普遍的です。

の 2 番目を次のように変更します。

for( 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]);
}
于 2014-06-28T19:40:57.377 に答える
3

あなたの疑似コードは、配列がインデックス 1 [1] で始まると想定していると思います。C および C++ では、配列はゼロ [0] で始まります。

于 2014-06-28T19:38:40.607 に答える
2

疑似コードは、C++ が使用する 0 ベースのインデックスではなく、1 ベースのインデックスを使用していると思います。

于 2014-06-28T19:38:47.120 に答える