Time and Space Complexity

時間計算量:

• 最良、平均、最悪の場合: O(n²)
  • 選択ソートは、配列がすでにソートされている場合でも、最小値を見つけるために常に未ソート部分全体をスキャンします。比較の回数は入力の順序に依存しません。

空間計算量:

• O(1)
  • 選択ソートは「インプレース（in-place）」アルゴリズムです。入力の大きさに関わらず、一定量の追加メモリのみを使用して要素を並べ替えます。

まとめ:

• 選択ソートはシンプルでメモリ効率が良いです。
• スワップ（入れ替え）の回数が少なく（最大で n-1 回）、書き込みコストが高い場合に有用です。
• 二乗の時間計算量のため、大規模なデータセットには適しておらず、マージソートやクイックソートなどのアルゴリズムが好まれます。