3

私は実際に、並べ替えられた配列を持っているが、いくつかの数字が逆になっているという問題を解決しようとしています。例: 1 2 3 4 9 8 7 11 12 14は配列です。

さて、私の最初の考えは、Binary Searchアルゴリズムを適用してPEAK ( a[i]>a[i+1] && a[i]>a[i-1])

ただし、必ずしも正しい結果が得られるとは限りません。さらに、リストはほとんどソートされているため、効率的ではない可能性があります。

次のインプレッション :Insertion Sortリストがソートされているので適用し、挿入ソートはそのような場合に最適なパフォーマンスを発揮します。

誰でもより良い解決策を提案できますか、それとも私の解決策が正しいかどうか? 効率的または非効率的?

PS - これは宿題ではありません。

UPDATE : 挿入ソート (この場合は O(n)) または線形スキャンでサブシーケンスを見つけてから、それを逆にします (O(n))。最適化できる可能性はありますか? または、おそらく O(logn) で行いますか？

4

5 に答える 5

4

最初の反転 (つまりa[i+1] < a[i]) を直線的に検索し、そのインデックスを呼び出しますinv1。反転が停止するまで続行し、最後の index を呼び出しますinv2。inv1と の間で配列を逆にしinv2ます。

あなたの例でinv1は、4であり、inv26です。配列要素はゼロから番号が付けられます。

このアルゴリズムは、元のエントリの数に比例します。

于 2012-07-30T15:50:26.567 に答える
3

反転した埋め込みサブシーケンスを除いてリストがソートされていることが確実な場合は、単純なスキャンを実行して、反転したサブシーケンスの開始を検出し (最初の反対方向の変化を見つけることによって)、最後までスキャンすることをお勧めします。サブシーケンスの（変更が正しい方向を再開する場所）サブシーケンスを逆にします。これは、重複しない限り、複数のサブシーケンスに対しても機能するはずです。複雑さは O(n) である必要があります。

于 2012-07-30T15:49:14.383 に答える
1

注: {4,9} の間でカットするか、{9,8} の間でカットするかを決定する必要があります。（1つだけ追加します;-）

#include <stdio.h>

int array[] = {1,2,3,4,9,8,7,11,12,14};

unsigned findrev(int *arr, unsigned len, unsigned *ppos);
void revrev(int *arr, unsigned len);

unsigned findrev(int *arr, unsigned len, unsigned *ppos)
{
unsigned zlen,pos;

for(zlen=pos=0; pos < len-1; pos++ ) {
        if (arr[pos+1] < arr[pos]) zlen++;
        else if (zlen) break;
        }
if (zlen) *ppos = pos - zlen++;

return zlen;
}

void revrev(int *arr, unsigned len)
{
unsigned pos;
for (pos = 0; pos < --len; pos++) {
        int tmp;
        tmp = arr[pos];
        arr[pos] = arr[len] ;
        arr[len] = tmp;
        }
}

int main(void)
{
unsigned start,len;

len = findrev(array, 10, &start);
printf("Start=%u Len=%u\n", start, len);
revrev(array+start, len);

for (start=0; start < 10; start++) {
        printf(" %d", array[start] );
        }
printf("\n"  );

return 0;
}

注: 逆の実行の長さは、逆のシーケンスの最初の要素よりも大きい (または等しい) 最初の値のバイナリ検索によっても見つけることができます。

于 2012-07-30T16:15:05.887 に答える
0

n 個の数値のリストで、以下の例のように n/2 個の数値が逆ソートされている場合、n/2 個の数値を反転する必要があるため、線形解 [O(n)] が最良の解であると思います。 n)。

また、この場合も同様のシーケンスの場合、最悪の場合、挿入ソートは O (n^2) ではなく O (n) になると思います。

例: 以下の分布を持つ配列を考えて、挿入ソートを使用しようとします。

n/4 並べ替えられた数値 | n2 逆ソートされた数値 | n/4 並べ替えられた数値

n/2 逆ソートされた数値の場合、ソートの複雑さは O(n^2) になります。

于 2012-08-04T02:45:41.700 に答える
0

Timsort は、ほとんどが既にソートされている配列のソートに非常に優れています。さらに、2 つの異なるマージステップを使用して、どちらがうまく機能するかに応じてインプレース マージソートを実行します。私はそれが python と Java の標準ライブラリ、おそらく他のライブラリにあると言われています。ただし、おそらくループ内では使用しないでください。ループ内では、treap (良好な平均速度の場合) または red-black tree (低標準偏差の速度の場合) を使用することをお勧めします。

于 2012-07-30T17:10:15.753 に答える