容量nとn+mの 2 つの配列 (ソートされていない) があります。最初の配列にはn 個の要素があります。2 番目の配列にはm 個の要素があります (さらに、より多くの要素用にn 個の場所が予約されています)。
目標は、余分なスペースを使用せずに、2 つの配列をマージし、結果をソートされた方法で 2 番目の配列に格納することです。
現在、クイックソートを使用して両方の配列をソートしてから、マージソートを使用してそれらをマージしています。これを達成するためのより効率的な方法はありますか???
容量nとn+mの 2 つの配列 (ソートされていない) があります。最初の配列にはn 個の要素があります。2 番目の配列にはm 個の要素があります (さらに、より多くの要素用にn 個の場所が予約されています)。
目標は、余分なスペースを使用せずに、2 つの配列をマージし、結果をソートされた方法で 2 番目の配列に格納することです。
現在、クイックソートを使用して両方の配列をソートしてから、マージソートを使用してそれらをマージしています。これを達成するためのより効率的な方法はありますか???
明らかに最善の方法は、N の内容を N+M 配列の空き領域にコピーし、N+M 配列をクイックソートすることです。
2 つのクイックソートを実行してからマージ ソートを実行すると、操作全体の効率が低下します。
長さ M の配列をソートする必要がある場合、それを 2 つの配列 M1 と M2 に分割し、それぞれをソートしてからマージソートしますか? いいえ。そうすると、クイックソートの各呼び出しで利用できる情報が制限され、プロセスが遅くなります。
では、なぜ 2 つの開始配列を別々にしておくのでしょうか?
マージソートを調べることができます。
https://www.google.com/search?q=mergesort&ie=UTF-8&oe=UTF-8&hl=en&client=safari#itp=open0
または、サイズによっては、各配列でクイックソートを実行してから、マージソート手法 (またはマージしてからクイックソート) を使用してそれらをマージできます。
私はmergesortを使用します。基本的には、各配列を個別にソートしてから、それらを順番に並べることで機能します
マージソートでは O(nlogn) 、クイックソートでは O(nlogn) を見ていますが、クイックソートでは O(n^2) の最悪のケースが考えられます。
小さい方の配列を N 配列、もう一方の配列を M 配列と呼びましょう。M 配列の要素は、最初は 0 から m-1 の位置にあると想定しています。好みの手法を使用して両方の配列を並べ替えます。これは、安定性や最悪の場合の動作の制限などの他の基準に依存する場合があります。
if min(N) > max(M)
copy N's elements over starting at location m [O(n) time]
else
move M's elements to the end of the M array (last down to first) [O(m) time]
if min(M) > max(N)
copy N's elements over starting at location 0 [O(n) time for the copy]
else
perform classic merge: min of remaining m's and n's gets migrated
to next available space in M [O(min(m,n) time]
全体として、これは最初の並べ替え時間が支配的であり、マージ フェーズはすべて線形です。m を M 配列の末尾に移行すると、スペースの衝突がないことが保証されるため、仕様に従って追加のサイド ストレージは必要ありません。