選択法による並べかえ

整数の配列の並べ替え

二分探索では予めデータが整列されている必要がありました。ここでは、整数の配列を例にしていろいろな整列のアルゴリズム(やり方)を考えます。

まず、例にする配列です。

int[] data = { 44, 86, 24, 57, 78, 65, 39 };

これは次のように配列に収められています。

data[0] data[1] data[2] data[3] data[4] data[5] data[6]
44 86 24 57 78 65 39

これを次のように並べ替えます

data[0] data[1] data[2] data[3] data[4] data[5] data[6]
24 39 44 57 65 78 86

整列法2. 選択法による並べかえ

一番小さいものを選択して、先頭のものと交換する、残りのうち一番小さいものを選択して、先頭から2番目と交換する...を繰り返します。

ファイル名 SSort01.java

public class SSort01 {
    public static void main( String[] args ) {
        int[] data = { 44, 86, 24, 57, 78, 65, 39 };
                     // 0,  1,  2,  3,  4,  5,  6
        int min,sonoi;
        for( int k=0; data.length-1>k; k++ ){
            min = data[k];
            sonoi = k;
            for( int i=k+1; data.length>i; i++ ) {
                if( min > data[i] ){
                    min  = data[i];
                    sonoi = i;
                }
            }
            data[sonoi] = data[k];
            data[k] = min;
        }
        for (int i = 0; data.length>i; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }//mainの終わり
}//classの終わり

コンパイルと実行は次のようにします。

$ javac SSort01.java 
$ java SSort01 
24 39 44 57 65 78 86 
$ 

途中経過を表示する

初期値を書いたあと、二重のforの内側のiが一回りしたら、dataの値とkの値を表示します

ファイル名 BSort02.java

public class SSort02 {
    public static void main( String[] args ) {
        int[] data = { 44, 86, 24, 57, 78, 65, 39 };
                     // 0,  1,  2,  3,  4,  5,  6
        int min,sonoi;
        print(data);
        System.out.println(": 初期値");
        for( int k=0; data.length-1>k; k++ ){
            min = data[k];
            sonoi = k;
            for( int i=k+1; data.length>i; i++ ) {
                if( min > data[i] ){
                    min  = data[i];
                    sonoi = i;
                }
            }
            data[sonoi] = data[k];
            data[k] = min;
            print(data);
            System.out.printf(": k=%2d\n",k );
        }
        for (int i = 0; data.length>i; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }//mainの終わり
    
    static void print(int[] data){
        for (int x = 0; data.length>x; x++) {
            System.out.printf("%4d",data[x]);
        } 
    }//printの終わり
}//classの終わり

コンパイルと実行は次のようにします。

色をつけたところは、まだ並べていない範囲その中の最小値です。

$ javac SSort02.java 
$ java SSort02
  44  86  24  57  78  65  39: 初期値
  24  86  44  57  78  65  39: k= 0
  24  39  44  57  78  65  86: k= 1
  24  39  44  57  78  65  86: k= 2
  24  39  44  57  78  65  86: k= 3
  24  39  44  57  65  78  86: k= 4
  24  39  44  57  65  78  86: k= 5
24 39 44 57 65 78 86 

dataの値を変化させても並べ替えがうまく行く事を確認しなさい。(プログラムを変更したら再コンパイルする)

大きい順に並べ替える

SSort02.java をもとに書き換えて SSort03.java を作ります。

ファイル名 BSort03.java の変更点

1.クラス名を変更

public class SSort03 {

2.一番大きな値をさがすので、minをmaxにする。(これは人間にわかりやすくのため。minのままでも結果はかわらない)

        int max,sonoi;

3.ここも 2.と同じ

            max = data[k];

4.maxに覚えておいた暫定の一番大きい数値より大きいものが出てきたら、それを覚える。

                if( data[i] > max ){
                    max  = data[i];

コンパイルと実行は次のようにします。

$ javac SSort03.java 
$ java SSort03
  44  86  24  57  78  65  39: 初期値
  86  44  24  57  78  65  39: k= 0
  86  78  24  57  44  65  39: k= 1
  86  78  65  57  44  24  39: k= 2
  86  78  65  57  44  24  39: k= 3
  86  78  65  57  44  24  39: k= 4
  86  78  65  57  44  39  24: k= 5
86 78 65 57 44 39 24