選択ソート(Selection Sort)とは|図解や実装例でわかりやすく解説!

https://cdn-ak.f.st-hatena.com/images/fotolife/M/MDaiki/20211015/20211015113430.png

選択ソートとは

選択ソートとは, 各計算ステップで整列させたいデータ列の最小値を選択し並べるソートアルゴリズムです.

アルゴリズム

selectionSort(Array, N)
    for i が 0からN-1まで
        minj = i
        for j が i からN-1まで
            if A[j] < A[minj]
                minj = j
        A[i]とA[minj]を交換
変数 説明
Array[N] サイズNの整数型配列
i 未ソートの部分列の先頭を示すループ変数
minj i番目からN-i番目までの要素の中で最小の値
j ソート済み部分列からvarを挿入するための位置を探すループ変数

図解

配列 {4, 7, 3, 7, 2, 9}に対して選択ソートを行う. f:id:MDaiki:20211015110725p:plain

未ソート部分(黒のバーより右)から最小の値②を見つける. 次に,最小の値②と未ソート部分の先頭④を入れ替える, f:id:MDaiki:20211015111214p:plain

未ソート部分の先頭の黒のバーの位置を右に1つずらす. 未ソート部分から最小の値③を見つける. 次に,最小の値③と未ソート部分の先頭⑦を入れ替える, f:id:MDaiki:20211015111411p:plain

未ソート部分の先頭の黒のバーの位置を右に1つずらす. 未ソート部分から最小の値④を見つける. 次に,最小の値④と未ソート部分の先頭⑦を入れ替える, f:id:MDaiki:20211015111702p:plain

未ソート部分の先頭の黒のバーの位置を右に1つずらす. f:id:MDaiki:20211015111926p:plain 最小の値が未ソート部分の先頭にいるので何もしない.

未ソート部分の先頭の黒のバーの位置を右に1つずらす. f:id:MDaiki:20211015112202p:plain 最小の値が未ソート部分の先頭にいるので何もしない.

終了

計算量

 
データ数Nとすると最小値を求めるために,  N-1回, N-2回, N-3回...1回と比較演算を行う. そのため,  O(N^2)となる.

C++での実装例

問題

長さNの整数型の数列Aが与えられます. 挿入ソートで昇順で並べ替えなさい.

Sample Input

5
2 3 8 4 2

Sample Output

2 2 3 4 8

Answer

#include <iostream>

void selectionSort(int A[], int N) {
    for(int i = 0; i < N; i++){
        int minj = i;
        for(int j = i; j < N; j++){
            if(A[j] < A[minj]){
                minj = j;
            }
        }
        std::swap(A[i],A[minj]);
    }
}


int main() {
    int N;
    std::cin >> N;
    int A[N];
    for(int i = 0; i < N; i++){
        std::cin >> A[i];
    }
    selectionSort(A,N);
}

資料

google slideで資料も作ったのでよかったらこちらも参考に!! Google Slide : 選択ソート