C++ での最速の並べ替えアルゴリズム

1. C++ での最速の並べ替えアルゴリズム
2. アルゴリズムの複雑さに関するチートシート

この記事では、どの並べ替えアルゴリズムがどのような条件で最適に機能するかについて説明します。 条件には、データ構造のタイプ、ソートされるデータのサイズ、データの配置、およびデータ要素の範囲が含まれます。

まず、並べ替えアルゴリズムについて説明しましょう。 次に、さまざまなデータ構造におけるさまざまなアルゴリズムのパフォーマンスについて説明します。

C++ での最速の並べ替えアルゴリズム

ソートアルゴリズムは、任意のデータ構造に格納されている要素を配置する方法です。

ソートアルゴリズムの適合性は、入力データのサイズ、データ構造のタイプ、データの配置、時間と空間の複雑さ、およびデータの範囲によって異なります。

並べ替えアルゴリズムには、配列データ構造に対してより優れたパフォーマンスを発揮するものもあれば、ヒープに対してより優れたパフォーマンスを発揮するものもあります。 さらに、レコードの最上位の整数キーがレコードの数よりもはるかに小さい場合 (カウント ソートなど)、一部のアルゴリズムは高速です。

では、最速のアルゴリズムはどれですか? 答えは簡単に思えますが、複雑さの表を見て、時間の複雑さが最も低いもの (つまり、漸近的な成長) を選択してください。

ただし、実際には、アルゴリズム A がアルゴリズム B よりも優れたパフォーマンスを発揮する、またはアルゴリズム A がアルゴリズム B よりもパフォーマンスが優れていると直接言うことはできません。

したがって、特定の基礎となるデータ構造に対するさまざまなシナリオでの特定の適合性を備えた並べ替えアルゴリズムについて説明することにより、答えに対応しようとします。

データ構造 - リンクされたリスト

リンクリストは、ノードにデータを格納する線形データ構造です。 ノードは、データと次のノードへのポインタを含むリンク リストの基本的な構成要素です。

リンク リストをソートする最適なソート アルゴリズムは、マージ ソートです。 マージ操作の出力を格納するための補助配列が必要ないため、マージ ソートは配列よりもリンクされたリストで優れたパフォーマンスを発揮します。

配列とは異なり、連結リスト ノードはメモリ内で連続している必要はありません。 代わりに、ノードをさまざまなメモリ位置に分散させることができます。

また、配列とは対照的に、連結リストの中央に O(1) 追加スペースと O(1) 時間で値を配置できます。

その結果、リンク リストのソート中にマージ ソートのマージ操作を実装するために、追加の漸近的に増加するスペースは必要ありません。 したがって、マージソートはリンクリストを (nlog n) でソートします。

マージソートの実装は こちら にあります。

データ構造 - 配列

配列は、連続したメモリ位置にデータを格納する線形データ構造です。 配列内のデータの型は同じでなければなりません。

以下は、さまざまなソート アルゴリズムとその適切性の一覧です。

• 挿入ソートは、配列のソートされた領域に新しいアイテムを追加するときにほとんどアイテムを移動しないため、配列がほぼソートされている場合に選択できます。

  ソートされた配列での挿入ソートの時間計算量は O(n) ですが、同じ配列でのクイック ソートの時間計算量は O(n^2) です。 詳細については こちら をご覧ください。

・クイックソートはその場でソートするので、配列に向いています。 また、クイック ソート アルゴリズムは、ソート手順中に追加のスペースを必要としません。
・ マージソートの場合、追加スペースの獲得と解放が必要です。 したがって、マージソートアルゴリズムの実行時間は増加します。

平均して、マージとクイック ソートは `O(nlogn)` 時間の複雑さがありますが、マージ ソートは余分な `O(n)` スペースを必要とします。 ここで、`n` はソートされる配列のサイズです。 詳しくは [こちら](https://www.geeksforgeeks.org/why-quick-sort-preferred-for-arrays-and-merge-sort-for-linked-lists/) をご覧ください。

• 配列に格納されたデータ (整数、単語、固定サイズの文字列など) を 辞書式 順に並べ替えたい場合は、基数並べ替えを使用します。 基数ソートは、並列マシンを使用するときに実行されます。
• レコードの最大整数キーがレコード数よりもはるかに小さい場合、カウンティング ソートが使用されます。
• バケット ソートは、配列に格納されたデータが範囲内で均等に分散されている場合に最も効率的です。

データ構造 - ツリー

ツリーは、ノードにデータを格納する非線形データ構造です。 一番上のノードは root ノードと呼ばれます。 root ノードはさらに child ノードに接続されます。

ツリーにはさまざまな種類がありますが、ここでは二分探索ツリー (BST) についてのみ説明します。

ツリー ソートは、BST の最適なソート アルゴリズムと考えられています。 また、BST のインオーダー トラバーサルは、要素をソートされた順序で提供します。 同様に、ヒープ ソートは、ヒープに格納された要素をソートするのに最適です。

ハッシュ テーブル、赤黒木 など、他の種類のデータ構造のすべての並べ替えアルゴリズムも分析できることを思い出してください。

次のセクションでは、さまざまな並べ替えアルゴリズムの複雑さと安定性を示すチート シートを示します。

アルゴリズムの複雑さに関するチートシート

表を見る前に、ソート アルゴリズムに関連する一般的な用語について説明します。

安定ソート

キー間に同点の場合でも、キーの元の順序が維持される場合、アルゴリズムは安定しています。 たとえば、S シーケンスに次のペアがあるとします。

S = <(1,"Alex"), (3,"Bill"),(2,"Ananth"), (1, "Jack")>

ここで、上記のシーケンスを整数キーでソートしたいとします。 次に、安定した並べ替えアルゴリズムは、上記のシーケンスを次のように並べ替えます。

Stably Sorted S = <(1,"Alex"),(1, "Jack"),(2,"Ananth"),(3,"Bill")>

見てください、安定した並べ替えはペア (1, "Alex") と (1, "Jack") の元の順序を保持します。 ただし、不安定な並べ替えはそれを保証しません。

インプレースソート

一定量の補助メモリを必要とする場合、ソートは適切です。 これは、問題のサイズが大きくなっても追加のメモリ要件が増加しないことを意味します。

たとえば、以下のチート シートの O(1) スペースの複雑さを持つすべての種類が適切に配置されています。

基本的な並べ替えの用語について十分な背景知識を得た後、並べ替えアルゴリズムの複雑さの表を見てみましょう。 この表は、特定の問題のコンテキストで最適な並べ替えアルゴリズムを選択するための決定に役立ちます。