1. 序章
リンクリストは、その比較的単純なため、コンピュータサイエンスで一般的に見られるデータ構造です。
このチュートリアルでは、リンクリストを並べ替える最も効率的な方法を紹介します。
2. リンクリスト
リンクリストを使用する利点の1つは、要素の挿入と削除に隣接する要素の一定時間（つまり）の更新のみが必要なのに対し、配列などの他の構造ではコレクション内の要素の並べ替えが必要になることです。
逆に、要素のアクセスまたはルックアップは線形時間（つまり、リストのサイズです）で行われます。これは、ターゲット要素を見つけるためにアイテムの参照をトラバースする必要があるためです。 これは、ソートの特性が悪いと見なされます。これは、一般的な「スワップ」操作の効率が低く、リストのポインターがメモリ内に分散する可能性があるためです。 これにより、理論的には、配列と比較した場合の並べ替えのパフォーマンスが低下します。
3. リンクリストをソートするための最速のアルゴリズム
リンクリストの2つの比較並べ替えアルゴリズムを検討します。 比較アルゴリズムは、一般的な場合のソートアルゴリズムの下限である時間計算量によって制限されます。 また、オプションとして非比較基数ソートを検討します。
- Quicksort ：分割統治法の非安定ソートアルゴリズム。ピボットを使用して、リストをピボットよりも大きい要素と小さい要素で構成される再帰的にソートされたサブ配列に分割します。
- マージソート：分割統治の安定したソートアルゴリズムで、リスト内のすべての要素のサブリストを再帰的に作成します。
- 基数ソート（バケットソートまたはデジタルソートとも呼ばれます）は、非比較の非安定ソートアルゴリズムです。
3.1. 定性分析
マージは、一定の補助スペース要件を持つリンクリストに実装できるため、低スペースを必要とする問題に最適です。一般的に、マージソートはリンクリストに最適です。 これは、メモリへのランダムアクセスが少なくて済むアルゴリズムの性質によるものです。
クイックソートは高速ですが、信頼性が低い場合があります。 配列のクイックソートは、リンクリストよりも優れたオプションです。 配列のルックアップ時間は、リンクリストよりも高速です。 リンクリストを配列に変換すると、メモリ内のポインタの分散によりリンクリストを使用するときにキャッシュミスが発生する可能性が高くなるため、キャッシュ最適化の使用を有効にすることで速度を向上させることもできます。次にリンクリストを配列に変換したり、元に戻したりするためのスペースと実行時の要件を考慮する必要があります。
特定の特別な状況では、基数ソートはの対数よりも小さい可能性があるため、大きなリストのソートに適しています。 基数ソートの速度はコンテキストによって異なりますが、キーサイズはアルゴリズムの時間計算量に影響し、ソートする必要のあるオブジェクトのタイプによって異なります。
3.2. 定量分析
基数ソートは大きなリストの特定の問題に適しているため、以下のベンチマークでは考慮しません。 いくつかの洞察を与えるために、Python3でリンクリストと配列のクイックソートとリンクリストのマージソートをベンチマークします。 マージソートアルゴリズムは、反復的なボトムアップアプローチです。 表の列に示されているように、さまざまなサイズに対してソートが5回実行されます。 5回の実行の結果が平均化されます。 以下の表で結果を確認できます。
リンクリストのマージソートの結果は、再帰的アプローチを示していない可能性があります。 ただし、再帰的アプローチには大量の再帰的呼び出しが必要であり、大きなリストの並べ替えには適していません。
4. 結論
ソートアルゴリズムの効率は、ソートする必要のあるオブジェクトのタイプ、リストの長さ、およびソートアルゴリズムが動作する環境の詳細によって異なります。 比較的小さなキーサイズで表すことができる要素のリストが大きい場合は、基数ソートが最適な場合があります。 スペースの制限と安定した並べ替えの要件がある場合、またはリンクリストを純粋に並べ替えたい場合は、マージ並べ替えが最適なオプションです。
最後に、リンクリストを配列に変換してクイックソートを使用するのが最速の解決策かもしれません。
