【基本情報】独学マラソン ソートアルゴリズム Day 9

ナガノさんは足るを知り尽くしている

この記事は自分用の備忘録です。

ソートはアルゴリズムの基本

ソートの種類、あなたはいくつ言えますか？

バブルソート

• 隣り合う要素を比較しながら、必要に応じて大小を入れ替える方法
• シンプルだが、リストのサイズが大きいと処理時間が増えるので効率が悪い
• 例：
  • 1回目
    • [3, 5, 8, 4, 2] → [3, 5, 8, 4, 2] → [3, 5, 4, 8, 2] → [3, 5, 4, 2, 8]
  • 2回目
    • [3, 5, 4, 2, 8] → [3, 4, 5, 2, 8] → [3, 4, 2, 5, 8]
  • 3回目
    • [3, 4, 2, 5, 8] → [3, 2, 4, 5, 8]
  • 4回目
    • [2, 3, 4, 5, 8]

クイックソート

• 分割統治法を利用
• 基準値（ピボット）を選んで、それより小さい値と大きい値に分割することを繰り返す
• バブルソートよりも高速
• 例：
  • [5, 3, 8, 4, 2]
    • ピボット：5
      • 左 [3, 4, 2]、右 [8]
  • 左側 [3, 4, 2]
    • ピボット：3
      • 左 [2]、右 [4]
  • 各部分を結合: [2, 3, 4] + [5] + [8]

マージソート

• データを分割し、最小の単位からソート、マージを繰り返す
• 処理時間がデータの並びに依存しないので安定する
  • [1,4,3,2]と[1,2,4,3]の場合でも、同じ処理時間になる
• 例：
  • データ：[1, 4, 3, 2]
  • 分割
    • [1, 4] と [3, 2]
      • [1]、[4]、[3]、[2]
  • マージ
    • [1] と [4] をマージ → [1, 4]
    • [3] と [2] をマージ → [2, 3]
    • [1, 4] と [2, 3] をマージ → [1, 2, 3, 4]

選択ソート

• リストの中から最小の要素を探し、それをリストの先頭に持ってくる操作を繰り返す
• マージソートと同様に、処理時間がデータの並びに依存しないので安定する
• 操作回数が多いため、大規模なデータには不向き
• 例：
  • [5, 3, 8, 4, 2]
    • 2を5と入れ替え
      • [2, 3, 8, 4, 5]
  • [3, 8, 4, 5]
    • 入れ替え不要
  • [8, 4, 5]
    • 4と8を入れ替え
      • [4,8,5]
  • [8,5]
    • 8と5を入れ替え
      • [5,8]
  • 結果[2,3,4,5,8]

挿入ソート

• 前から2個要素を取り出し、順序が逆なら入れ替えて、その後は1つずつ適切な位置に挿入することを繰り返す
• 既にある程度整列されているデータの場合、効率が良い
  • 運要素絡む感じ
• 例：
  • データ：[5, 3, 8, 4, 2]
  • 5と3を比較、入れ替え
    • [3, 5, 8, 4, 2]
  • 8を取り出し、[3,5]と比較
    • [3,5,8]
  • 4を取り出し、[3,5,8]と比較
    • [3,4,5,8]
  • 2を取り出し、[3,4,5,8]と比較
    • [2,3,4,5,8]

どれを使えばいいの？

• データが小規模
  • 挿入ソートや選択ソート
• データが大量
  • マージソートやクイックソート
• 特定の範囲に限定
  • 基数ソートやカウントソート

ソートはまだまだあるらしい

• ヒープソート
  • ヒープ（最大ヒープまたは最小ヒープ）を利用し、最大（または最小）要素を順に取り出してソートするアルゴリズム
• シェルソート
  • 挿入ソートの改良版。要素を一定間隔で比較してソートし、その間隔を徐々に狭めることで効率的にソートする
• カウントソート
  • 値の範囲が限定されているときに使用する非比較ソート
  • 各値の出現回数を数え、その回数に基づいてリストを再構築する
• 基数ソート
  • 各桁ごとにデータをソートする非比較ソート
  • 整数や文字列のソートに適している
• バケツソート
  • データを複数の「バケツ」に分け、それぞれのバケツ内でソートを行い、最終的にバケツの内容を結合する
• 蜘蛛ソート
  • 隣接する要素を比較して、順序が間違っていれば戻って入れ替える
  • バブルソートに似ているが、前後に移動する
• コムソート
  • バブルソートの改良版
  • 隣接する要素だけでなく、間隔を広げた要素同士を比較し、徐々に間隔を縮めながらソートする
• トポロジカルソート
  • 有向非巡回グラフ（DAG）のノードを順序づけるソート
  • タスクの依存関係を解消する際などに使用
• バケットソート
  • データをそれぞれの値に対応するバケツ（または穴）に入れ、そこから順番に要素を取り出す。データの範囲が狭い場合に有効

感想

ソートの種類がこんなにたくさんあるとは‥
対数(log)とか久々に見たよ‥

参考