【アルゴリズム】単純選択ソート｜基本情報技術者科目B対策

2023年4月から基本情報技術者の試験制度が変更されたものの科目B（旧：午後問題）の重要さは変わりません。

出題方式は「多肢選択式」で以前と同じですが、データ構造及びアルゴリズムが8割、情報セキュリティが2割の割合で出題される点が大きく変わっています。

合格基準点は600点以上/1000点満点中、つまり6割以上取れれば合格になります。

そんな科目Bのデータ構造及びアルゴリズムについて、基本となるソートの問題について考えてみましょう。

ソート（整列）とは？？
単純選択ソートとは？？
どんなときに使う？
単純選択ソートの実装例（プログラム）
まとめ

ソート（整列）とは？？

ソートとは、複数のデータが並んだ列を、何らかの順序に基いて順番通りになるよう並べ替える(整列させる)こと。
数値を大きい順または小さい順に並べたり、文字をアルファベット順や五十音順に並べたり、日時を古い順または新しい順に並べ替えることが該当する。

また、コンピュータによるデータ処理でソート（整列）手順を定式化したアルゴリズムをソートアルゴリズムと言っています。

ソートアルゴリズムにも種類があり、場面に応じた使い分けが必要です。

＜ソートアルゴリズム例＞

・単純交換ソート（バブルソート）

・単純選択ソート

・クイックソート

・ヒープソート　　等

単純選択ソートとは？？

単純選択ソートとは、「最小要素を先頭に移動し、2番目に小さい要素を先頭から２番目に移動させる、という作業を繰り返す」という整列手順・ソートアルゴリズムのことを指します。

例えば、リストを昇順に整列させる手順の場合、下記のようになる。

１．整列されていないデータの中から最小値を探す。
２．最小値と先頭の値（最初の要素）を入替。最小値が整列されたデータとなる。

　※最小値が先頭の場合はそのままで、入替は発生しません。
３．整列されていないデータの中から最小値を探す。

　※先頭の値（最初の要素）は除く。

４．最小値と2番目の要素を入替。最小値が整列されたデータとなる。

　※最小値が2番目の要素の場合はそのままで、入替は発生しません。

５．手順1〜4を繰り返す。

このように総当たりで比較を行い、条件に一致する交換を実行することでソート（整列）が完了される。

どんなときに使う？

単純選択ソートは、単純交換ソート（バブルソート）と同様に最終的には全ての値を探索していく必要があります。ただ、シンプルなアルゴリズムです。

単純交換ソート（バブルソート）に比べると、値の交換回数が少なくなるので処理は高速になります。

単純選択ソートの実装例（プログラム）

実装例は下記です。

Web上で実際にプログラムを動かすことができるサイトがあります。

色々プログラムをいじってみましょう！

Online PHP/Java/C++... editor and compiler | paiza.IO

＜実装例＞

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int[] data = {1, 4, 3, 7, 5, 2, 6};
        int min = 0;

        //単純選択ソートのプログラム（コメント）
        for(int i=0; i < data.length; i++) {
            min = i;
            for(int j =i+ 1; j < data.length; j++) {
                if(data[min] > data[j]){
                    min = j;
                }
            }
            int tmp = data[i];
            data[i] = data[min];
            data[min] = tmp;            
        }

        //配列を表示させるプログラム（コメント）
        for(int i = 0; i < data.length; i++) {
            System.out.println(data[i]);
        }
    }
}