sorting - キューを別のキューで並べ替える

Question

サイズNの別のキューと有限数の変数を使用して、サイズNのキューを並べ替えるにはどうすればよいですか？

ナイーブな実装-キューの最小値を見つけて空のキューにプッシュし、次に新しい最小値を見つけてプッシュするなどはO（n ^ 2）です。より効率的なアルゴリズムはありますか？

Answer 1

ナイーブな実装が機能するとは思わない。これはキューであるため、キューの最後にない場合、最小の要素を削除することはできません。

私が考えることができる唯一の方法は、2番目のキューを常にソートしておくことです。1.q1から要素を削除します。2.この要素>=q2の最後の要素である場合は、q2に挿入します。（このように、q2はまだソートされています）。3.それ以外の場合は、q1に挿入し直します。q1が空になるまで、上記の手順を繰り返します。

Answer 2

これは、私が頭のてっぺんから思いついた簡単なロジックです。最悪の場合の実行時間は O(N^2) ですが、理想的には最良の場合は O(N) になります。即興のロジックで複雑さをさらに軽減できると思います。

構文は Javascript ですが、わかりやすいようにコメントが付けられています。

これが役立つことを願っています。

// SORT A QUEUE USING ANOTHER QUEUE
function sortQueueUsingQueue(uq) {
    // instantiate required variables
    var sq = new Queue();
    var t = null, last = null;
    // copy the items to a temp queue
    // so as not to destroy the original queue
    var tq = new Queue(uq);
    // loop until input is not empty
    while(!tq.isEmpty()) {
        t = tq.dequeue();
        if (last && last <= t) {
            // new element will be at the end of the queue, and we don't have to
            // process any further - short-circuit scenario
            // this is the best case scenario, constant time operation per new item
            sq.enqueue(t);
            // also keep track of the last item in the queue,
            // which in this case is the new item
            last = t;
        } else {
            // other scenario: linear time operation per new item
            // new element will be somewhere in the middle (or beginning) so,
            // take elements from the beginning which are less or equal to new item,
            // and put them at the back
            while(!sq.isEmpty() && sq.peek() <= t) {
                sq.enqueue(sq.dequeue());
            }
            // when that is done, now put the new element into the queue,
            // i.e the insertion into the proper place
            sq.enqueue(t);
            // following which, shift the rest elements to the back of the queue,
            // to reconstruct the sorted order,
            // thus always keeping the second queue sorted per insertion
            while(sq.peek() > t) {
                // meanwhile, also keep a track of the last (highest) item in the queue
                // so that we may perform a short-circuit if permitted
                last = sq.dequeue();
                sq.enqueue(last);
            }
        }

    }
    return sq;
}

ここで作業コード全体を github gist として表示できます: https://gist.github.com/abhishekcghosh/049b50b22e92fefc5124

Answer 3

私のアルゴリズム:

 let the Q size = n, 
 1 save = getRearValue(1stQ)
 2 pop the element from 1st Q and insert it into 2nd Q.
 3 if getFrontValue(1stQ) > getRearValue(2ndQ)  
 4        then goto step 2.
 5 else 
 6        pop the element from 1st Q and insert back into the same Q (1st Q). 
 7        if (save != getRearValue(1stQ)) goto step 3.
 8 if (1st Q not sorted OR getFrontValue(1stQ) > getFrontValue(2ndQ))
 9          then 
 10          pop all elements of 2nd Q and insert into 1st Q (One by one).
 11          goto step 1.
 12 else
 13     pop all elements of 2nd Q and insert into 1st Q (One by one).
 14     return 1stQ