🎯

【Java】選択ソート

2024/03/06に公開

Java

初心者

tech

選択ソートとは

選択ソートとは、要素を順番に見ていき、最小値（または最大値）の要素を見つけ出し、その要素を配列の先頭から順に並べ替えていくソートアルゴリズムです。
選択ソートは、要素数が多い場合や、配列の要素がほぼ整列されている場合には、効率が悪いという欠点もあります。

問題の内容と回答の方針等

問題
- サイズnの数列aを選択ソートせよ。
条件
- 最小値の要素をn-1回取り出すと、最後の要素は最大値の要素が残るので、処理しなくてよい。
解答方針
- 数列aを配列a[]で管理します。
- 最小値の要素をn-1回取り出します。
- i回目では、要素a[i]から最後の要素a[n-1]の間の最小値の要素を取り出します。但し、iの初期値は0とします。
- 暫定最小値のインデックスを保存する変数をminIndexとし、iで初期化します。
- 変数jがi+1からn-1のループを回し、a[j]<a[minIndex]であれば、変数minIndexを変数jに更新します。
- a[i]とa[minIndex]を交換します。
今回の入力値
上からn、aとする。
```
4
8 1 3 2
```

選択ソートのコード例

import java.util.Scanner;

public class Main {
    static void print(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            if (i > 0)
                System.out.print(" ");
            System.out.print(a[i]);
        }
        System.out.println();
    }

    static void selectionSort(int[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            // 変数minIndexを定義
            int minIndex = i;
            // jがi+1からn-1までのループ処理を行う
            for (int j = i + 1; j < n; j++) {
                // a[j] < a[minIndex]なら
                if (a[j] < a[minIndex]) {
                    // minIndexをjに更新する
                    minIndex = j;
                }
            }
            // a[i]とa[minIndex]を交換する
            int min = a[minIndex];
            a[minIndex] = a[i];
            a[i] = min;
            
            print(a, n);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        selectionSort(a, n);
    }
}

選択ソートアルゴリズムの解説

選択ソートアルゴリズムに該当する下記の部分のみを解説します。

static void selectionSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {

        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        int min = a[minIndex];
        a[minIndex] = a[i];
        a[i] = min;
        
        print(a, n);
    }
}

仮引数は下記の通りです。

a = [8, 1, 3, 2]
n = 4

i = 0 の場合

外側のfor文の条件式i=0 < n-1=3を満たすので、
変数minIndexに、iの0を代入します。
内側のfor文の条件式j=1 < n=4を満たすので、
if文の条件式a[1]=1 < a[0]=8を満たすので、
変数minIndexに、jの1を代入します。
内側のfor文の条件式j=2 < n=4を満たすので、
if文の条件式a[2]=3 < a[1]=1を満たさないので、このif文を抜けます。
内側のfor文の条件式j=3 < n=4を満たすので、
if文の条件式a[3]=2 < a[1]=1を満たさないので、このif文を抜けます。
内側のfor文の条件式j=4 < n=4を満たさないので、このループを抜けます。
変数minにa[1]の1を代入します。
a[1]にa[0]の8を代入します。
a[0]に変数minの1を代入します。
この時の配列aは下記の通りになります。
```
a = [1, 8, 3, 2]
```
printメソッドを呼び出し、実引数として配列aと変数nを渡します。

i = 1 の場合

外側のfor文の条件式i=1 < n-1=3を満たすので、
変数minIndexに、iの1を代入します。
内側のfor文の条件式j=2 < n=4を満たすので、
if文の条件式a[2]=3 < a[1]=8を満たすので、
変数minIndexに、jの2を代入します。
内側のfor文の条件式j=3 < n=4を満たすので、
if文の条件式a[3]=2 < a[2]=3を満たすので、
変数minIndexに、jの3を代入します。
内側のfor文の条件式j=4 < n=4を満たさないので、このループを抜けます。
変数minにa[3]の2を代入します。
a[3]にa[1]の8を代入します。
a[1]に変数minの2を代入します。
この時の配列aは下記の通りになります。
```
a = [1, 2, 3, 8]
```
printメソッドを呼び出し、実引数として配列aと変数nを渡します。

i = 2 の場合

外側のfor文の条件式i=2 < n-1=3を満たすので、
変数minIndexに、iの2を代入します。
内側のfor文の条件式j=3 < n=4を満たすので、
if文の条件式a[3]=8 < a[2]=1を満たさないので、このif文を抜けます。
内側のfor文の条件式j=4 < n=4を満たさないので、このループを抜けます。
変数minにa[2]の3を代入します。
a[2]にa[2]の3を代入します。
a[2]に変数minの3を代入します。
この時の配列aは下記の通りになります。
```
a = [1, 2, 3, 8]
```
printメソッドを呼び出し、実引数として配列aと変数nを渡します。

選択ソートとは

問題の内容と回答の方針等

選択ソートのコード例

選択ソートアルゴリズムの解説

i = 0 の場合

i = 1 の場合

i = 2 の場合

Discussion