選択ソートとは？シンプルで交換回数の少ないソートアルゴリズムを図解で解説

アルゴリズム

2024.07.04

選択ソートとは
1. アルゴリズムの概要
性能
1. 時間計算量
2. 空間計算量
特徴
実装(Python)
参考文献

選択ソートとは

選択ソートとは、

数列を昇順に並び替えるアルゴリズムの1つ

です。

選択ソートは、リストの中から最小（または最大）の要素を選び、それを順に並べていく直感的なソートアルゴリズムです。

アルゴリズムの概要

左側にソート済みの部分を作成し、未ソートの中で最小の要素を未ソート部分の先頭に配置していきます。

挿入ソートのアルゴリズム

- ステップ1
  
  未ソート部分の最小の要素を見つける
- ステップ2
  
  最小の要素を未ソートの先頭と入れ替えて、ソート済みとする
- ステップ3
  
  未ソートの部分がなくなるまでステップ1,2を繰り返す

性能

時間計算量

時間計算量は以下の通りです。

時間計算量

平均時間計算量: \(O(N^2)\)
データの初期配置に影響せず常に同じ計算量となる

空間計算量

空間計算量は、 \(O(1)\)（インプレース実装可能）

特徴

長所

実装が簡単
小さなデータセットに効果的(オーバヘッドが少ないため)

短所

大きなデータセットに対しては非効率(O(n^2)のため)
安定ソートでない（同じ値の要素の相対的な順序が保たれない）

用途

要素の交換するコストが高いアプリケーション

実装(Python)

def selection_sort(nums):
    for unsorted_top in range(len(nums) - 1):
        min_index = unsorted_top
        for i in range(unsorted_top, len(nums)):
            if nums[i] < nums[min_index]:
                min_index = i
        nums[unsorted_top], nums[min_index] = nums[min_index], nums[unsorted_top]
        

nums = [4, 2, 3, 1]
selection_sort(nums)
print(nums)