0

こんにちは、線形ではなく二分探索を使用して挿入ソートを改善するように依頼されました。問題は、データ比較により、最良のケースが O(n) ではなく O(n log n) になったことです。これにより、場合によっては遅くはないにしても、プログラムが同等になりました。これが私のバイナリ挿入ソートコードです:

void InsertionSort(int data[], int size)
{
    int index = -1;
    for(int i = 1,temp,j;i<size;i++)
    {
        temp = data[i];//DM O(N)
        int high = i,low = 0,mid;//DM O(N)
        while(low <= high)//DC O(nlogn)
        {
            mid = (low + high) /2;
            if(temp < data[mid])
            {
                high = mid - 1;
                index = mid;
            }

            else if (temp > data[mid])
            {
                low = mid + 1;      
            }

            else if(data[mid] == temp)
            {
                index = mid;
                break; 
            } 

        }
        for(j = i;j > index;j--)
        {
            data[j] = data[j-1];//DC Worst Case O(n*n) but the exact is summation of n(n+1) / 2 nad best case o(1)
        }
        data[j] = temp;//DM O(n)
    }   
}
4

3 に答える 3

0

最良のケースを優先する偏った段階で二分探索を開始できます。に直接移動する代わりに、(low+high)/2位置から開始し、i-1次に、、、、...より小さい要素が見つかるまで、または より低くなるまで。次に、通常の二分探索を続けます。i-2i-4i-8i-16i-32i-whateverlow

この最適化にはコストがかかることに注意してください。最良のケース --- ソートされたデータまたはほぼソートされたデータ --- には O(N) 時間がかかりますが、平均的なケースと最悪のケースでは、単純な二分探索バージョンと比べて少し遅くなります。

void InsertionSort (int data[], int size)
{
    int i, j, high, low, mid, hop;
    int temp;

    for (i=1; i<size; i++)
    {
        temp = data[i];

        high = i;
        low = 0;
        hop = 1;

        do
        {
            mid = high - hop;
            hop <<= 1;

            if (temp < data[mid])
                high = mid;
            else
                low = mid + 1;
        }
        while (low+hop <= high);

        while (low != high)
        {
            mid = (low + high) / 2;

            if (temp < data[mid])
                high = mid;
            else
                low = mid + 1;
        }

        for(j=i; j>low; j--)
            data[j] = data[j-1];

        data[j] = temp;
    }   
}

また、 ではなくhighが割り当てられていることにも注意してください。の場合は の場合とまったく同じように扱われます。これは、挿入ソートの優れた特性を維持するためです。これは安定したソートです。ただし、プレーン整数をソートする場合は違いはありません。midmid+1temp==data[mid]temp>data[mid]

于 2013-03-04T21:23:48.137 に答える
-1

最後の else :else if(data[mid] == temp)を simpleに置き換えることもできます。else これは、前の 2 つが true でない場合に is が true であることは明らかであるためです...

于 2013-03-03T14:50:02.030 に答える