5

[これはインタビューの質問です。重複が見つかりませんでした。]

配列には、2つのサブソートされた配列が含まれます。2つのサブ配列をソートするためのインプレースアルゴリズムを提供します。

例：I / P：1 4 5 7 8 9 2 3 6 10 11 O / P：1 2 3 4 5 6 7 8 9 10 11

インプレースマージソート、挿入ソート（サブ配列はすでにソートされているため）、およびクイックソートの観点から考えましたが、標準のソート方法を使用するよりも複雑なソリューションを考えることはできませんでした。

ソートされたサブ配列プロパティを活用して、入力でクイックソートを実行するよりも時間計算量を増やすことができるアルゴリズムを見つけるのを手伝ってください。

これは、次の例を使用して、私が考えたマージソートシミュレーションです。

  1) For position 0, Comparing 1 & 2, 1 is smaller let it stay at it's original place
  2) For position 1, Comparing 2 & 4, 2 is smaller so swap 2 and 4
  3) For position 2, Comparison now is between 4 and 3 (5 > 4 anyways) swap 3 and 5
  4) For position 3, Comparison between 4 & 5, swap 4 and 7
  5) For position 4, Comparison between 7 & 5, swap 8 and 5 
  6) For position 5, Comparison between 7 & 8 (OUCH!!) it should have been between 7 & 6

この問題は、インプレースマージが複雑すぎる行列の並べ替えられた行の並べ替えに似ているようです。

4

4 に答える 4

6

この正確な問題を解決するための線形時間アルゴリズムと、その解決策を考え出すのにどれだけの労力が費やされたかについては、http：//comjnl.oxfordjournals.org/content/38/8/681.full.pdf+htmlを参照してください。

私の推測では、インタビュアーは彼らがうまくいったと思ったかわいい答えを持っていたと思いますが、実際にはそうではありません。2番目に良い推測は、彼らが理由で複雑さを指定しなかったということです。

インタビューで私は実際に「これを効率的に行う方法はわかりませんが、その質問についての研究はあると確信しています。しかし、ここに非効率的な答えがあります」と言ったでしょう。それから私は明らかにうまくいく何かをするでしょう。

于 2013-03-14T16:42:22.463 に答える
4

O（n log n）の最悪の場合の動作をするインプレースマージソートがありますが、論文が述べているように、「関連する一定の要因のため、アルゴリズムは主に理論的に重要です」。https://stackoverflow.com/a/2571104/56778を参照してください

ソートされたサブ配列の1つと同じ大きさの一時バッファーを割り当てることができない場合、インプレースマージは非常に困難です。

于 2013-03-14T03:48:51.343 に答える
0

インタビューの質問の場合、アルゴリズムでは、スワップすると、結果の配列は個別にソートされなくなります。大きなスワップされた要素が正しい位置に到達するまで「バブル」してから続行する必要があります。

簡単にするために、topAとtopBを現在の位置として2つの配列を考えてみましょう（最初は両方とも0です）。必要な結果の配列をA[1..m]..B[1..n]とします。これが擬似コードです：

if (A[topA] < B[topB]) {
    swap (A[topA], B[topB])
    index = topB;
    while (B[index] < B[index + 1]) {
        swap(B[index], B[index + 1])
    }
    topB++
} else {
  topA++;
}

上記の各実行の最後に、結果の配列がソートされて小さくなります。これは、アレイの1つがなくなるまで続けることができます。ただし、バブリングフェーズのため、複雑さはO（m + n）よりも大きくなります。

于 2013-03-14T05:23:03.677 に答える
0 
    // since both are sorted use array b as min heap
    // if a[i] > b[0] (top of min-heap), exch it and heapify b
    // order : O(nlog(n))
   void inplaceMerge(vector<int>& a, vector<int>& b)
   {
     for (int i=0; i < a.size(); i++)  {
         if (a[i] > b[0]) {
                swap(a[i], b[0]);
                sink(b, 0, b.size()-1); // bubbleDown() operation in heap() 
         }
      }
      sort(b.begin(), b.end());   
    }

   void sink(vector<int>& b, int i, int n)
   {
            int j = 2*i + 1;
            while (j <= n) {
                 if (j+1 < n && b[j+1] < b[j]) j++;
                 if (b[j] < b[i]) swap(b[i], b[j]);
                 else break;
                 i = j;
                 j = 2*i + 1;
            }
   }
于 2013-07-25T12:29:19.923 に答える