ネットサーフィンした時偶々下記のURLが見つかったので、
バブルソートを勉強しようと思った。
URL:http://www.mkyong.com/java/java-bubble-sort-example/
ブログ主が書いたバブルソートの定義：
Bubble sort is the simplest sorting algorithm,
it compares the first two elements,
if the first is greater than the second, swaps them, continues doing (compares and swaps) for the next pair of adjacent elements.
It then starts again with the first two elements, compares,
swaps until no more swaps are required.
グッグルして見つかったバブルソートの定義、
->配列内隣り合うふたつの要素の値を比較して
条件（値が大きか小さいか）に応じた交換を行う整列アルゴリズム
例えば、
インプットが1597253の場合だと、
バブルソートを実装したプログラムによってアウトプットが1235579になる。
自分が実装するアルゴリズムを考えてみたが、
まず、
左側から一番目の数字と二番目の数字の大きさを比べ、
左側の数字が大きい場合->右側の数字との位置を交換する
右側の数字が大きい場合->交換しなくて済む
また、
二番目と三番目との大きさを比べ、
位置を交換するかしないかを判断し、
同じように、
三番目VS四番目、四番目VS五番目。。。
六番目と七番目と大きさ比べ、第一ラウンドが終わる。
そして、
第二ラウンドが始まる。
一番目と二番目と大きさを比べ、
二番目と三番目との大きさを比べ。。。
同じように六番目と七番目と大きさを比べ、
第二ラウンドが終わる。
同じ流れで、
このまま第三ラウンド、第四ラウンド。。。
最後は第六ラウンド
自分がアルゴリズムを考えて実装して見た
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length;//配列の長さ
//IF 前の数字>後の数字
//数字の位置を交換する際、前の数字を暫く保存するためのVariable
int temp;
//配列の中各数字を比べる必要があり、
// 上記書いた各ラウンドも実行する必要があり二重ループを書く
for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
//if 前>後 位置を交換する
if(input[j]>input[j+1]){
temp = input[j];//前の数字を暫くVariableに保存
input[j] = input[j+1];//後ろの数字を前の数字の位置に移動
input[j+1] = temp; //前の数字（Variableに保存中）を後ろに移動
}
}
}
return input;
}
}
テスト結果:
122345 , 正確
交換回数を考える
下記をやって数字の交換回数を計算
・数字の位置を交換する回数を計算しプリント
・交換後の配列をプリント
static int[] sort(int[] input){
int count = 0;
int length = input.length;
int temp;
for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
if(input[j]>input[j+1]){
temp = input[j];
input[j] = input[j+1];
input[j+1] = temp;
count++;
//交換後の配列の元素をプリント
System.out.print("count:" + count + " ");
for(int a:input){
System.out.print(a);
}
System.out.println();
}
}
}
System.out.println(count);
return input;
}
Output：
count:1 123254
count:2 122354
count:3 122345
3 = 交換回数:
最悪の場合だと、
配列の数字の順序が543221で数字の大きさを比べると必ず交換。
配列の数字が6つなので交換回数が
第一ラウンド：5
第二ラウンド：4
第三ラウンド：3
第四ラウンド：2
第五ラウンド：1
合計：15
因みに、
この場合は比較回数と交換回数が同じ。
プログラムのチューニング
ここで一つ気づいたけど、
上記の僕が書いたプログラムは実は効率がよくないこと。
原因は、
配列がすでに昇順したものの、
まだ数字の大きさを比較する可能性がある。
比較回数を計算すればわかる。
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length;//配列の長さ
//IF 前の数字>後の数字
//数字の位置を交換する際、前の数字を暫く保存するためのVariable
int temp;
//比較回数を計算用
int count = 0;
//配列の中各数字を比べる必要があり、
//上記書いた各ラウンドも実行する必要があり二重ループを書く
for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
//数字大きさ比較する際、配列の元素をプリント
count++;
System.out.print("count:" + count + " ");
for(int a:input){
System.out.print(a);
}
System.out.println();
//if 前>後 位置を交換する
if(input[j]>input[j+1]){
temp = input[j];//前の数字を暫くVariableに保存
input[j] = input[j+1];//後ろの数字を前の数字の位置に移動
input[j+1] = temp; //前の数字（Variableに保存中）を後ろに移動
}
}
}
return input;
}
}
Output:
count:1 213254
count:2 123254
count:3 123254
count:4 122354
count:5 122354
count:6 122345
count:7 122345
count:8 122345
count:9 122345
count:10 122345
count:11 122345
count:12 122345
count:13 122345
count:14 122345
count:15 122345
count:16 122345
count:17 122345
count:18 122345
count:19 122345
count:20 122345
count:21 122345
count:22 122345
count:23 122345
count:24 122345
count:25 122345
count:26 122345
count:27 122345
count:28 122345
count:29 122345
count:30 122345
122345
三回比較し配列がすでに昇順になったのに、
プログラムがまだ続いて効率が悪い。
解決としては、
配列が昇順の状態かを確認。
URLでの方法を確認し、
boolean is_sorted；とのVariableを使った。
説明を見ると、
// is sorted? then break it, avoid useless loop.
もしソート済みの状況ならプログラムを終止させ、
無駄なループが生じないようにする。
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length;//配列の長さ
//IF 前の数字>後の数字
//数字の位置を交換する際、前の数字を暫く保存するためのVariable
int temp;
//比較回数を計算用
int count = 0;
Boolean is_sorted;
//配列の中各数字を比べる必要があり、
//上記書いた各ラウンドも実行する必要があり二重ループを書く
for(int i=0;i<length;i++){
//ラウンドが始まる前にTrueに設定、もし比較する行為をしない場合ループ終止
is_sorted = true;
for(int j=0;j<length-1;j++){
//数字大きさ比較する際、配列の元素をプリント
count++;
System.out.print("count:" + count + " ");
for(int a:input){
System.out.print(a);
}
System.out.println();
//if 前>後 位置を交換する
if(input[j]>input[j+1]){
temp = input[j];//前の数字を暫くVariableに保存
input[j] = input[j+1];//後ろの数字を前の数字の位置に移動
input[j+1] = temp; //前の数字（Variableに保存中）を後ろに移動
//交換行為をしたらFalseに変更、
//配列がまだ昇順になってないとのこと
is_sorted = false;
}
}
if (is_sorted) break;
}
return input;
}
}
Output：
count:1 213254
count:2 123254
count:3 123254
count:4 122354
count:5 122354
count:6 122345
count:7 122345
count:8 122345
count:9 122345
count:10 122345
122345
時間複雑度
数字がN個の場合、
第一ラウンドの比較回数が少なくともN回
第二ラウンドの比較回数も少なくともN回
時間複雑度(worst case)＝O(n²)
その他：
僕が外人なので日本語の表現が変な場合、
教えてもらえば助かります。
2019/2/16
時間複雑度、自分が考えたアルゴリズムで数字の比較回数を間違えていて訂正。