二分探索では予めデータが整列されている必要がありました。ここでは、整数の配列を例にしていろいろな整列のアルゴリズム(やり方)を考えます。
まず、例にする配列です。
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 |
隣同士を順番に比較して、逆順になっていたら取り替えるという操作を繰り返します。
一般にバブルソートと呼ばれているアルゴリズムですが、一つ比較した後、次はどの隣を比較するかでいろいろな流儀があります。一例だけ示します。
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の値を表示します
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 を作ります。抹消線が引いてある部分は削除します。
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を作り、結果が同じ事を確認しなさい。
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 という名前で保存しなさい。
直すところは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