交換法による並べかえ

整数の配列の並べ替え

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

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

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

整列法1. 交換法による並べかえ

隣同士を順番に比較して、逆順になっていたら取り替えるという操作を繰り返します。

一般にバブルソートと呼ばれているアルゴリズムですが、一つ比較した後、次はどの隣を比較するかでいろいろな流儀があります。一例だけ示します。

ファイル名 BSort01.java

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

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

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

途中経過を表示する

二重のforの内側のiが変化したら、dataの現在の値とn,iの値を表示します

ファイル名 BSort02.java

public class BSort02 {
    public static void main( String[] args ) {
        int[] data = { 44, 86, 24, 57, 78, 65, 39 };
                     // 0,  1,  2,  3,  4,  5,  6
        for( int k=0; data.length-1>k; k++ ){
            for( int i=0; data.length-1>i; i++ ) {
                print(data);
                System.out.printf(": k=%2d i=%2d\n",k,i );
                if( data[i] > data[i+1] ){
                    int tmp   = data[i];   //この3行で値の交換
                    data[i]   = data[i+1];
                    data[i+1] = tmp;
                }
            }
        }
        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の終わり

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

色をつけたところは、data[i]とdata[i+1]の部分です。これから比較して逆なら交換します。

$ javac BSort02.java 
$ java BSort02 
  44  86  24  57  78  65  39: k= 0 i= 0
  44  86  24  57  78  65  39: k= 0 i= 1
  44  24  86  57  78  65  39: k= 0 i= 2
  44  24  57  86  78  65  39: k= 0 i= 3
  44  24  57  78  86  65  39: k= 0 i= 4
  44  24  57  78  65  86  39: k= 0 i= 5
  44  24  57  78  65  39  86: k= 1 i= 0
  24  44  57  78  65  39  86: k= 1 i= 1
  24  44  57  78  65  39  86: k= 1 i= 2
  24  44  57  78  65  39  86: k= 1 i= 3
  24  44  57  65  78  39  86: k= 1 i= 4
  24  44  57  65  39  78  86: k= 1 i= 5
  24  44  57  65  39  78  86: k= 2 i= 0
  24  44  57  65  39  78  86: k= 2 i= 1
  24  44  57  65  39  78  86: k= 2 i= 2
  24  44  57  65  39  78  86: k= 2 i= 3
  24  44  57  39  65  78  86: k= 2 i= 4
  24  44  57  39  65  78  86: k= 2 i= 5
  24  44  57  39  65  78  86: k= 3 i= 0
  24  44  57  39  65  78  86: k= 3 i= 1
  24  44  57  39  65  78  86: k= 3 i= 2
  24  44  39  57  65  78  86: k= 3 i= 3
  24  44  39  57  65  78  86: k= 3 i= 4
  24  44  39  57  65  78  86: k= 3 i= 5
  24  44  39  57  65  78  86: k= 4 i= 0
  24  44  39  57  65  78  86: k= 4 i= 1
  24  39  44  57  65  78  86: k= 4 i= 2
  24  39  44  57  65  78  86: k= 4 i= 3
  24  39  44  57  65  78  86: k= 4 i= 4
  24  39  44  57  65  78  86: k= 4 i= 5
  24  39  44  57  65  78  86: k= 5 i= 0
  24  39  44  57  65  78  86: k= 5 i= 1
  24  39  44  57  65  78  86: k= 5 i= 2
  24  39  44  57  65  78  86: k= 5 i= 3
  24  39  44  57  65  78  86: k= 5 i= 4
  24  39  44  57  65  78  86: k= 5 i= 5
24 39 44 57 65 78 86 
$ 

無駄を省く

k=0の回を終わると、一番大きい86が最後に来ています。k=1のi=5で78と86を比べていますが、86は一番大きいのがわかっていますから、これは無駄です。kの繰り返しが終わるたびに、大きい方からひとつずつ値が確定していることを次のプログラムで確認します。

BSort02.java の赤い下線部を変えて BSort03.java を作ります。抹消線が引いてある部分は削除します。

ファイル名 BSort03.java

public class BSort03 {
    public static void main( String[] args ) {
        int[] data = { 44, 86, 24, 57, 78, 65, 39 };
                     // 0,  1,  2,  3,  4,  5,  6
        for( int k=0; data.length-1>k; k++ ){
            for( int i=0; data.length-1>i; i++ ) {
                print(data);
                System.out.printf(": k=%2d i=%2d\n",k,i );
                if( data[i] > data[i+1] ){
                    int tmp   = data[i];   //この3行で値の交換
                    data[i]   = data[i+1];
                    data[i+1] = tmp;
                }
            }
            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 BSort03.java 
$ java BSort03
  44  24  57  78  65  39  86: k= 0の回目終了
  24  44  57  65  39  78  86: k= 1の回目終了
  24  44  57  39  65  78  86: k= 2の回目終了
  24  44  39  57  65  78  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 
$ 

k=0の回では、i=0からi=5まで繰り返します。i=5のとき、5と6の比較になります。

   0   1   2   3   4   5   6 
   44  86  24  57  78  65  39 :初めの値

k=0の回の終了で、86は確定です。次のk=1の回ではi=5は不要です。i=4で4と5の比較になります。

   0   1   2   3   4   5   6 
   44  24  57  78  65  39  86: k= 0の回目終了

k=1の回の終了で、78 86が確定です。次のk=2の回ではi=4は不要です。i=3で3と4の比較になります。

   0   1   2   3   4   5   6 
   24  44  57  65  39  78  86: k= 0の回目終了

つまり

k=0 では i=0 〜 i=5  つまり、 i=0; data.length-1-0>i
k=1 では i=0 〜 i=4  つまり、 i=0; data.length-1-1>i
k=2 では i=0 〜 i=3  つまり、 i=0; data.length-1-2>i
....

と考えて

i=0; data.length-1-k>i

とすれば、無駄を省くことができます。

無駄を省くプログラム

BSort03.java の次の部分を変更して、BSort04.javaを作り、結果が同じ事を確認しなさい。

ファイル名 BSort04.java の一部

public class BSort04 {
    public static void main( String[] args ) {
        int[] data = { 44, 86, 24, 57, 78, 65, 39 };
                     // 0,  1,  2,  3,  4,  5,  6
        for( int k=0; data.length-1>k; k++ ){
            for( int i=0; data.length-1-k>i; i++ ) {
         ......

降順にする

降順は大きい順です。BSort04.javaまでは小さい順になっているので昇順といいます。

BSort01.java から BSort04.java まで、どれか一つを元にして、下記の?の部分を変更するだけで降順になります。考えましょう。

変更したら必ず1行目の class の後のBSort01やBSort04 を BSort05 に直してから、「別名で保存」を選び、BSort05.java という名前で保存しなさい。

ファイル名 BSort05.java の一部

直すところは2ヶ所です。

一つ目

public class BSort05 {

2つ目

        if( data[j] ? data[j+1] ){

コンパイルと実行は次のようにします。(表示はBSort04 を使った場合です)

$ javac BSort05.java 
$ java BSort05
  86  44  57  78  65  39  24: k= 0の回目終了
  86  57  78  65  44  39  24: k= 1の回目終了
  86  78  65  57  44  39  24: k= 2の回目終了
  86  78  65  57  44  39  24: k= 3の回目終了
  86  78  65  57  44  39  24: k= 4の回目終了
  86  78  65  57  44  39  24: k= 5の回目終了
86 78 65 57 44 39 24