リンクリストをマージソートする方法
1. 概要
このチュートリアルでは、マージソートアルゴリズムを使用してリンクリストをソートする方法について説明します。
まず、問題を定義し、それを説明する例を示します。
次に、この問題に対する2つのアプローチについて説明します。
2. 問題の定義
複数のノードで構成されるリンクリストがあり、各ノードに2つの値が格納されているとします。
- ：ノードに格納されている値を表します。
- ：これは、リスト内の現在のノードの後に続く次のノードへのポインターを表します。
私たちのタスクは、マージソートアルゴリズムを使用してこのリンクリストをソートし、リストの各ノードが前のすべてのノードの値よりも大きい値を持つようにすることです。
理解を深めるために例を確認してみましょう。 次のリンクリストがあるとします。
指定されたリンクリストを並べ替えると、次のリンクリストが表示されます。
ご覧のとおり、各ノードの値は前のすべてのノードの値よりも大きくなっています。
3. 再帰的アプローチ
3.1. 本旨
このアプローチでは、リストの中央ノードの値をに等しくすることにより、指定されたリンクリストを2つに分割します。次に、各呼び出しの最後に、各半分で再帰ソート関数を個別に呼び出します。ソートされた2つの半分をマージして、リンクリストをソートします。
3.2. 実装
実装を3つの機能に分割します。 まず、リストの真ん中の要素を返す関数を実装します。 次に、2つのソートされたリストを誰がマージするかを確認します。 最後に、完全なアルゴリズムについて説明します。
3.3. リンクリストの真ん中を取得
実装を見てみましょう：
この関数は、リンクリストの中間ノードを返します。
低速と高速の2つのポインタを定義しました。 毎回、遅いポインターは1ステップ前進し、速いポインターは2ステップ前進します。 したがって、高速ポインタは低速ポインタの2倍の距離を移動します。つまり、高速ポインタがリンクリストの最後に到達すると、低速ポインタはリンクリストの中央に配置されます。
3.4. 2つのソートされたリンクリストをマージする
実装を見てみましょう：
この関数は、2つのソートされたリストを1つのソートされたリンクリストにマージします。
最初に、リンクリストとを宣言しました。これは、の終わりへのポインタです。
次に、現在のポインタが等しくない間、2つの状況を維持する必要があります。
- ：は、リストの現在のノードの値がノードの値以下であるため、リストのノードの前に配置する必要があることを意味します。 したがって、は現在のノードである必要があり、ポインタを次のノードに移動します。
- ：次に、が現在のノードになり、ポインタを次のノードに移動します。
その後、のにを追加します。
ポインタの1つがリストの最後に達すると、ループから抜け出します。 次に、ポインタの1つがまだに等しくないかどうかを確認し、そのリストの残りを。の最後に追加します。
最後に、マージされたリストのヘッドポインタであるを返します。
3.5. マージリンクリストの並べ替え
実装を見てみましょう：
この関数は、マージソートアルゴリズムを使用してリンクリストをソートします。
まず、が等しいかどうかを確認し、次にリストが空になります。 同様に、がに等しい場合、これは、指定されたリストに単一のノードがあることを意味します。 どちらの場合も、ソートされたバージョンのリストは最初のバージョンと同じであるため、を返します。
次に、関数を使用してリストの中央ノードを取得します。 次に、指定されたリストを2つの部分に分割します。
- ：ポインタから始まります。
- ：中間ノードの後に開始します。
その後、真ん中のノードからリストを2つに分割することに等しいようにします。
最終的には、各パーツを個別に並べ替えてから、それらをマージして1つの並べ替えられたリストを取得します。
3.6. 複雑
ここでの時間と空間の複雑さはです。この複雑さの背後にある理由を調べてみましょう。
まず、関数には複雑さがあり、リストの各ノードを最大で1回反復します。ここで、はリストの長さです。
第2に、関数には複雑さがあり、各リストのノードを最大で1回反復します。ここで、は最初のリストの長さと2番目のリストの長さです。
最後に、関数には各呼び出しで複雑さの原因があります。2つのリストを複雑さでマージします。再帰ツリーの深さは、各呼び出しでリストを2つに分割するためです。ここで、はリストの長さです。
つまり、全体の複雑さは .
4. 反復アプローチ
4.1. 本旨
このアプローチでは、指定されたリンクリストを2の累乗のサイズの並べ替えられたブロックに分割し、2つの連続するブロックごとにマージします。
まず、リストをサイズ1のブロックに分割し、次に2つの連続するブロックごとにマージして、サイズ2のブロックを並べ替えます。
次に、リストをサイズ2のブロックに分割し、2つの連続するブロックごとにマージして、サイズ4のブロックを並べ替えます。
ブロックサイズが指定されたリンクリストの長さ以上の2の累乗に達するまで、これらの手順を実行し続けます。その時点で、リンクリストが並べ替えられます。
4.2. 実装
実装を2つの機能に分割します。 最初のブロックは2つのブロックをマージする役割を果たし、2番目のブロックは完全なアルゴリズム自体です。
4.3. 2つのブロックをマージする
実装を見てみましょう：
この関数は、特定のサイズの2つのソートされたブロックをマージします。 この関数のパラメーターは、最初のブロックの先頭とそのサイズへのポインターです。 さらに、2番目のブロックにも同じものを渡します。 最後に、リンクリストとその最後へのポインタを渡します。
ブロックの1つが空でない限り、これらのブロックにはまだいくつかの未使用のノードがあることを意味するため、複数の手順を実行します。
最初に、を宣言します。これは、リストの最後のノードの後に来るはずのノードを格納します。
次に、ブロックが空であるか、またはブロック内に未取得のノードがまだあるかどうかをチェックする関数を呼び出します。 さらに、現在のノードの値が現在のノードの値以下であるかどうかをチェックします。つまり、ノードはノードの前にある必要があります。
その場合、ノードをに割り当て、ブロックのサイズを1つ減らして、ポインタを次のノードに移動します。 それ以外の場合は、が1つになります。 ブロックのサイズを1つ減らし、ポインタを次のノードに移動します。
最後に、equalを作成してノードをブロックから切り取り、リンクリストの最後に追加します。
4.4. マージリンクリストの並べ替え
実装を見てみましょう：
最初に、リストを分割した後のリストの各ブロックのサイズを表すものと、2つの連続するブロックごとにマージした後のマージされたブロックの数を表すものを宣言します。
次に、指定されたリンクリストの長さ以上の2の累乗に達しない限り、次の手順を実行する必要があります。
- の値をゼロにリセットします。
- リンクリストの先頭を指す左右のポインタを最初に宣言します。
- リストをクリアします。
- 左側のブロックサイズがより小さく、ポインタがリストの最後に到達していませんが、ポインタをリストの次のノードに移動し、左側のブロックのサイズを1つ増やします。 これで、情報は最初のブロックの先頭にあり、ポインターは2番目のブロックの先頭にあります。
- 最初と2番目のブロックをマージします。
- マージ後のポインタが2番目のブロックの後に続くブロックの先頭を指しているので作成します。
- リスト全体をマージするまで、これらすべての手順を繰り返します。つまり、リンクリストが並べ替えられます。
4.5. 複雑
ここでのスペースの複雑さはです。これは、同じリストを変更していて、追加のリストを作成していないためです。 この複雑さの背後にある理由を調べてみましょう。
時間計算量に関しては、リンクリストの長さ以上の2の累乗に達するまで、指定されたリンクリストをブロック時間に分割し続けます。 次に、各反復で、合計がに等しい2つの連続するブロックごとにマージします。
つまり、全体の複雑さは .
5. 結論
このチュートリアルでは、マージソートアルゴリズムを使用してリンクリストをソートする問題を示しました。 一般的な考え方を説明し、それを解決するための2つのアプローチについて説明しました。
