二分探索では予めデータが整列されている必要がありました。ここでは、整数の配列を例にしていろいろな整列のアルゴリズム(やり方)を考えます。
まず、例にする配列です。
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番目と交換する...を繰り返します。
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の値を表示します
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 を作ります。
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