基本情報対策：科目B「選択ソート」

選択ソートとは

対象となるデータの中から最小値（もしくは最大値）を探し先頭の値と交換、この作業を繰り返すことで全体を整列させていく手法です。 選択ソートは、未整列データ内の最小値と先頭の値を交換。 この作業を繰り返し整列していく整列アルゴリズム。

以下の場合に導入を検討する

①データセットが小さい場合:
データセットの要素数が比較的小さい場合に効果的です。データセットが少ない場合、選択ソートの実行時間は他の高度なソートアルゴリズムよりも短くなる傾向があります。


②追加のメモリ空間が制約されている場合:
追加のメモリ空間を必要としないアルゴリズムです。データセットをソートする際に追加のメモリを必要としないため、メモリの制約がある環境や組み込みシステムなどで使用されることがあります。


③安定性が重要でない場合:
同じ値を持つ要素の順序が変わる可能性があります。もし安定性が重要でなく、ソートの速度が優先される場合には、選択ソートが適切です。

ただし、データセットが非常に大きい場合やパフォーマンスが重要な場合には、選択ソートは効率的ではありません。そのような場合には、マージソートやクイックソートなどの高速なソートアルゴリズムが一般的に選択されます。

以下ソースコード

Main.java

import java.util.Arrays;

public class Main {
    public static int[] selectSortMachine(int[] array) {
        int min; //最小値を格納する変数
        int j;   //最小値を探索するためのカウント変数
        int tmp; //一時退避変数

//        ２重ループで実現する
//        １巡目は最小値を配列に格納する、min変数の初期化処理を行う。
//        ２巡目は最小値の検索を行う
        for (int i = 0; i < array.length-1; i++) {
            min = i; //ソート済み範囲は対象外となる為 iを格納する

//            j = i + 1をすることで同値の比較を避ける(処理性能UP)
            for (j = i + 1; j < array.length; j++) {
//                配列要素がarray[j]より小さい場合はminに格納する
                if (array[j] < array[min]) {
                    min = j; //現在の配列番号に格納されたデータを比べて小さい値を保持している場合は配列番号を更新する
                }
            }

//          最小値が決まったらminを格納する
            if(min != i){
                tmp = array[i];
                array[i] = array[min];
                array[min] = tmp;
            }

            System.out.println(Arrays.toString(array));
        }
        return array;
    }
}
    

TestMain.java

import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class MainTest {
    @Test
    public void testSelectSortMachine() {
        // テスト用のデータ
        int[] array = {5,4,2,3,1};
        // 期待される結果
        int[] expected = {1,2,3,4,5};
        // テスト対象のメソッドを実行
        int[] sortedArray = Main.selectSortMachine(array);
        // 期待される結果と実際の結果を比較
        assertArrayEquals(expected, sortedArray);

//[1, 4, 2, 3, 5]
//[1, 2, 4, 3, 5]
//[1, 2, 3, 4, 5]
//[1, 2, 3, 4, 5]
    }
}