ソートアルゴリズムの説明

並べ替えアルゴリズムは、配列またはリストを入力として受け取り、アイテムを特定の順序に配置する一連の命令です。

並べ替えは、最も一般的には数値またはアルファベット順(辞書式順序と呼ばれる)の形式であり、昇順(AZ、0-9)または降順(ZA、9-0)にすることができます。

ソートアルゴリズムが重要な理由

並べ替えは問題の複雑さを軽減できることが多いため、コンピュータサイエンスの重要なアルゴリズムです。これらのアルゴリズムは、検索アルゴリズム、データベースアルゴリズム、分割統治法、データ構造アルゴリズムなどに直接適用されます。

いくつかの一般的なソートアルゴリズム

最も一般的なソートアルゴリズムのいくつかは次のとおりです。

  • 選択ソート
  • バブルソート
  • 挿入ソート
  • マージソート
  • クイックソート
  • ヒープソート
  • ソートのカウント
  • 基数ソート
  • バケットソート

ソートアルゴリズムの分類

ソートアルゴリズムは、次のパラメータに基づいて分類できます。

  1. スワップまたは反転の数に基づくこれは、アルゴリズムが要素をスワップして入力をソートする回数です。Selection Sort最小数のスワップが必要です。
  2. 比較数に基づくこれは、アルゴリズムが要素を比較して入力をソートする回数です。Big-O表記を使用すると、上記の並べ替えアルゴリズムの例では、ほとんどの出力について、少なくともO(nlogn)最良の場合のO(n^2)比較と最悪の場合の比較が必要です。
  3. 再帰または非再帰に基づくなどの一部の並べ替えアルゴリズムは、Quick Sort再帰的な手法を使用して入力を並べ替えます。Selection Sortまたはなどの他のソートアルゴリズムは、Insertion Sort非再帰的な手法を使用します。最後に、などの一部の並べ替えアルゴリズムでMerge Sortは、再帰的手法と非再帰的手法の両方を使用して入力を並べ替えます。
  4. 安定性に基づくソートアルゴリズムはstable、アルゴリズムが等しいキーを持つ要素の相対的な順序を維持する場合と言われます。言い換えると、2つの同等の要素は、入力と同じ順序でソートされた出力に残ります。
  5. Insertion sortMerge Sort、そしてBubble Sort安定しています
  6. Heap SortかつQuick Sort安定していません
  7. 余分なスペース要件に基づくソートアルゴリズムは、ソートのためにin place一定のO(1)余分なスペースが必要な場合と言われています。
  8. Insertion sortそして、Quick-sortされているin place我々はピボット約要素を移動し、実際の入力の大きさは、ソート時の出力を格納するために予め割り当てられなければならないマージソートに当てはまらない別の配列を使用しないようにソート。
  9. Merge Sortは、out place操作のために追加のメモリスペースを必要とするため、ソートの例です。

比較ベースの並べ替えに最適な時間計算量

比較ベースのソートアルゴリズムでは、入力配列をソートするために少なくともnLog2nの比較を行う必要があり、ヒープソートとマージソートは漸近的に最適な比較ソートです。これは、決定木図を描くことで簡単に証明できます。