すずしんろぐ

読者です 読者をやめる 読者になる 読者になる

すずしんろぐ

人生大逆転を目指す、鈴木俊吾の成長日記

Java 選択ソート(Selection Sort)のプログラムを作成してみた

number

こんにちは、すずしんです。

今日は、アルゴリズムの勉強と肩慣らしの意味も込めまして…。 選択ソートのプログラムをJavaで作成してみました。

選択ソートとは?

選択ソートは、配列の中から最小値(最大値)を探して、配列の先頭要素と交換するということを繰り返すことで整列を行う方法です。 最悪計算量はO(n2)と遅いですが、実装が単純で分かりやすいためしばしば用いられます。 数あるソートアルゴリズムの中でも基本ですね。

sortメソッド

int型の配列を昇順に選択ソートするメソッドsort()を作成してみました。 ソースコードを見てもらえれば大体何をしているかは分かると思います。

簡単に説明すると、1回のループでは最小の数があるインデックスを探していきます。 そして、現在のインデックスとその最小値があるインデックスが違う場合、値の入れ替えを行います。 この操作を(要素数-1)回繰り返しています。

private static void sort(int[] n) {
    for(int i = 0; i < n.length-1; i++) {
        int index = i;
        for(int j = i + 1; j < n.length; j++) {
            if(n[j] < n[index]) index = j;
        }
        if(i != index) {
            int tmp = n[index];
            n[index] = n[i];
            n[i] = tmp;
        }
    }
}

サンプルプログラム

上記のsort()メソッドを実際に使用して選択ソートするサンプルプログラムを作成してみました。 int型配列nを用意し、その配列の要素を表示、選択ソート、その後要素を表示しています。 やっていることは非常に単純ですね。

public class SelectionSort {
    public static void main(String[] args) {
        int[] n = {3, 9, 4, 7, 2, 5, 1, 8, 0, 6};
        printArray(n);
        sort(n);
        printArray(n);
    }
    
    private static void sort(int[] n) {
        for(int i = 0; i < n.length-1; i++) {
            int index = i;
            for(int j = i + 1; j < n.length; j++) {
                if(n[j] < n[index]) index = j;
            }
            if(i != index) {
                int tmp = n[index];
                n[index] = n[i];
                n[i] = tmp;
            }
        }
    }
    
    private static void printArray(int[] n) {
        for(int i: n) System.out.print(i + " ");
        System.out.println();
    }
}

実行結果

サンプルプログラムの実行結果は以下のようになります。 正しく配列が昇順にソートされているのが分かると思います。

3 9 4 7 2 5 1 8 0 6 
0 1 2 3 4 5 6 7 8 9