0

線形検索の代わりにバイナリ検索を使用して挿入されるアイテムの正しい位置を見つける挿入ソートアルゴリズムである次のコードを実行しますが、結果に正しくソートされていない2つの数字があります!

#include <iostream>
using namespace std;

void insertion_sort (int a[], int n /* the size of array */)
{
    int i, temp,j;
    for (i = 1; i < n; i++)
    {
        /* Assume items before a[i] are sorted. */
        /* Pick an number */
        temp = a[i];

        /* Do binary search to find out the
           point where b is to be inserted. */

        int low = 0, high = i - 1, k;

        while (high-low>1)
        {
            int mid = (high + low) / 2;

            if (temp <= a[mid]) 
                high = mid;
            else 
                low = mid;
        }

        /* Shift items between high and i by 1 */
        for (k = i; k > high; k--)
            a[k] = a[k - 1];

        a[high] = temp;
    }
}


int main()
{
    int A[15]={9,5,98,2,5,4,66,12,8,54,0,11,99,55,13};
    insertion_sort(A,15);
    for (int i=0; i<15; i++)
        cout<<A[i]<<endl;
    system("pause");
    return 0;
}

出力：

ここに画像の説明を入力

なんで？

4

3 に答える 3

1

最も簡単な修正: initializelowおよびhighas int low = -1, high = i;. あなたがやりたかったのは、インデックスを見つけてlow、highから0までのすべての要素lowが <であり、 からまでa[i]のすべての要素が ≥であるようにすることでした。すべての要素が よりも大きい場合のコーナー ケースと、これらすべての要素が よりも小さい場合のコーナー ケースをキャプチャしなかったため、初期化は機能しませんでした。highi-1a[i]a[0], ..., a[i-1]a[i]a[i]

于 2013-11-10T14:14:23.747 に答える
1

ここで注意すべき点がいくつかあります。

  1. とにかくスペースを作るためにすべての要素をシフトする必要があるため、バイナリ検索では何も得られません。したがって、実際にはアルゴリズムの全体的なコストが増加します (ただし、漸近的ではありません)。

  2. これは C++ であるため、k が使用される for ループの前のどこでも k を宣言する必要はありません (単に use を使用しますfor(int k; ...))。

  3. アルゴリズムの開始を分析します: i=0 -> low = high = 0. したがって、while ループは実行されません。次に、要素を移動する必要があるかどうかに関係なく、for (k) ループは要素 0 と 1 を交換します。これがエラー番号 1 です。

  4. i の 2 回目の反復: 低 = 0 および高 = 1 であるため、while ループは再び実行されません。また、少なくとも要素 1 と 2 を入れ替えても、再度実行されません。エラー番号 2。

  5. ここで、次の反復ごとに、何があっても、最初はインデックス 0 (テスト コードでは =9) だった要素が、さらに最後のインデックスに移動することに注意してください。

そのため、最初の for(i) ループの 2 回の反復をチェックした直後に、a[i] の前の要素がソートされているという仮定が間違っていることがわかり、したがってアルゴリズムも間違っていることがわかります。

于 2013-11-10T14:03:23.767 に答える
1 
#include <iostream>
using namespace std;

void insertion_sort (int a[], int n /* the size of array */)
{
    int i, temp,j;
    for (i = 1; i < n; i++)
    {
        /* Assume items before a[i] are sorted. */
        /* Pick an number */
        temp = a[i];

        /* Do binary search to find out the
           point where b is to be inserted. */

最後に挿入する必要がある場合があるため、上限は範囲より上で、検索を除外する必要があります。つまり、何もしません。

        // int low = 0, high = i - 1, k;
        int low = 0, high = i, k;

ここでの条件はlow < high、ではなくlow + 1 < high

        // while (high-low>1)
        while (low < high)
        {
            int mid = (high + low) / 2;

            if (temp <= a[mid]) 
                high = mid;
            else

]がa[mid厳密に より大きい場合temp、挿入できる最低位置はmid + 1です。

                // low = mid;
                low = mid + 1
        }

        /* Shift items between high and i by 1 */
        for (k = i; k > high; k--)
            a[k] = a[k - 1];

        a[high] = temp;
    }
}


int main()
{
    int A[15]={9,5,98,2,5,4,66,12,8,54,0,11,99,55,13};
    insertion_sort(A,15);
    for (int i=0; i<15; i++)
        cout<<A[i]<<endl;
    system("pause");
    return 0;
}
于 2013-11-10T14:12:30.163 に答える