3

異なる整数の配列が与えられます。配列から要素を削除し、その要素を末尾に追加できます。これは 1 回の MOVE であり、1 回の MOVE 操作としてカウントされます。配列をソートするために必要な移動の最小数を見つけます。

4

3 に答える 3

14

私が理解しているように、要素を最後に移動すると、その1つの場所の後のすべての要素がシフトするため、3番目の要素を移動します

[a_1, a_2, a_3, a_4, a_5, a_6]

最後まで生産する

[a_1, a_2, a_4, a_5, a_6, a_3]

その理解が正しければ、最小の手数の戦略は

  1. 配列がソートされている場合は停止します。
  2. 配列内のより小さい要素の前に現れる最小の要素を見つける
  3. その要素を最後に移動します

  4. 1に行きます。

     Ex: 
  I/p: 8 6 1 7 5 2 3 9

 Process:
       8 6 1 7 2 3 9 5
       8 1 7 2 3 9 5 6
       8 1 2 3 9 5 6 7
       1 2 3 9 5 6 7 8
       1 2 3 5 6 7 8 9 -> sorted

   So totally 5 moves to be done to sort an array.

証明:各ステップで、配列内で昇順に配置された最終的な並べ替えられた配列の要素の最初のシーケンスが少なくとも 1 つ増加するため、アルゴリズムは終了します。アルゴリズムは、配列がソートされたときにのみ終了します。

各配列要素は、最大 1 回移動されます。要素vが iteration で移動された場合i、その後、すべての要素<= vが配列内で昇順で配置されます。要素を移動しても> vその相対的な配置は変わらないためv、後の反復で移動する要素として選択されません。

配列要素は、移動する最初の要素と少なくとも同じ大きさである場合にのみ移動されますv_1。

構造上、移動された要素は厳密に増加するシーケンスを形成するため、要素< v_1は移動されません。

を移動した後v_1、 より大きいすべての要素は、配列内のv_1より小さい要素 (つまりv_1、場合によっては他の要素) の前に配置されます。w > v_1要素の相対的な配置を変更する唯一の方法v_1は、最後に移動wすることです。したがって、あるステップwで移動する必要があります。

どのソート順序でも、すべての要素>= v_1を少なくとも 1 回は移動する必要があります。

v_1v_0 < v_1元の配列には後に配置されたがあり、とv_1の順序を変更する唯一の方法は 移動であるため、いくつかのステップで移動する必要があります。v_0v_1v_1

w > v_1上記により、移動後、少なくとも一度はすべて移動する必要がありますv_1。

必要な移動の数を見つけることは O(n) で行うことができますが、もちろん、並べ替え自体は 2 次です。

移動する最初の要素 を見つけた後、よりも小さい要素v_1の数を単純に数えると、必要な移動数は になります。kv_1n - k

v_1O(n) での発見: (私はもともと前向きに考えていましたが、後ろ向きであることが判明しました。後ろ向きに行けば簡単です。)

最初に、配列の最後から、局所的な最小値が見つかるか、配列の最初に到達するまでスキャンします。先頭に到達すると、配列は既にソートされており、移動は必要ありません。それ以外の場合は、(ローカル) 最小値の値と、直前の要素の値を暫定的な値 f として格納しますv_1。次に、配列の先頭に到達するまでさらに進み、各ステップで、現在の要素が小さい場合は最小値を更新し、現在のv_1要素が最小値よりも大きいが仮の要素よりも小さい場合は仮の値を更新しv_1ます。

int move_count(int *a, int n) {
    int j = n-1;
    while(j > 0 && a[j-1] < a[j]) --j;
    if (j == 0) return 0;   // the array is already sorted
    // min_val holds the smallest element in the array after
    // the currently investigated position, v_1 holds the smallest
    // element after the current position that is larger than any later
    int min_val = a[j], v_1 = a[j-1];
    j -= 2;
    while(j >= 0) {
        if (a[j] < min_val) {
            min_val = a[j];
        } else if (a[j] < v_1) {
            v_1 = a[j];
        }
        --j;
    }
    int count_smaller = 0;
    for(j = 0; j < n; ++j) {
        if (a[j] < v_1) ++count_smaller;
    }
    return n - count_smaller;
}
于 2012-07-27T16:12:04.210 に答える
1

解決策は、選択ソートに基づいています。http://www.sorting-algorithms.com/selection-sortでこのアニメーションを見て、アイデアをつかんでください。アイデアは、k 番目の反復で k 番目に大きい要素を見つけ、その要素で MOVE を呼び出すだけです。この要素を見つける方法は、アニメーションでも示されています。複雑さは O(n) です。

于 2012-07-27T05:09:32.000 に答える
0

MOVEが配列内の要素をシフトできる唯一の方法である場合、選択ソートは、k番目の要素を最後に移動してk番目の反復でk番目に小さい要素に置き換える方法です。

最小移動操作=0（配列がすでにソートされている場合）。
最大移動操作=n（配列が目的の逆順でソートされている場合）。
したがって、総移動操作= O（n）。

ソートアルゴリズムの複雑さは変わりません。

于 2012-07-27T13:20:57.587 に答える