今回はバブルソートを実装してみます。
バブルソートを検索すると様々な説明がありますが、自分は馬鹿なので全然理解できませんでした。
なんとか自分なりにコードを書き理解することができました。
バブルソートを自分なりに解釈すると「隣の数字同士を比較して、小さい（大きい）数字を左（右）に送り固定していく」といった感じに至りました。
では実際に作成したコードをご覧ください。
import java.util.*;
public class Algorithm {
public static void main(String[] args){
// 1から50の数字でランダムに10個選びソートする
Random r = new Random();
int[] array = new int[10];
for (int i = 0; i < array.length; i++) {
array[i] = r.nextInt(50);
}
print(array);
bubbleSort(array);
print(array);
}
static void bubbleSort(int[] array){
// arrayの長さ分ループさせる
for (int i = 0; i < array.length; i++){
// 長さ-1からiまで減らしてループする
for (int j = array.length - 1; j > i; j--){
// もしもj番目よりもj-1番目が大きかったら、値を交換する
// => 隣同士を比較していき、左側が大きかったら、値を交換する
if (array[j - 1] > array[j]){
int tmp = array[j - 1];
array[j - 1] = array[j];
array[j] = tmp;
}
}
}
}
static void print(int[] array) {
// arrayの中身を出力する
for (int i = 0; i < array.length; i++) {
if (i != 0) {
System.out.print(" ");
}
System.out.print(array[i]);
}
System.out.println();
}
}
最初のランダムの数字配列が「5, 4, 3, 2, 1」となった時、外側の1回目のループでは「1, 5, 4, 3, 2」、外側の2回目で「1, 2, 5, 4, 3」といった感じにソートされていきます。
array.length – 1から始めることで、後ろから走査でき、小さい数字を右に送ることができます。
内側のループで j > i までとなっているのは、「1, 2, 5, 4, 3」の赤文字部分はすでに決まっているため動かす必要がないためです。
もしも大きい数字から並べたい時は、i = array.length – 1、j = 0として不等号や符号を逆にすれば良いだけです。（結果的にソートされるのは変わらないです。）
static void bubbleSort2(int[] array){
// 大きい数字から並べる
for (int i = array.length - 1; i > 0; i--){
for (int j = 0; j < i; j++){
System.out.println(i + " " + j);
if (array[j + 1] < array[j]){
int tmp = array[j + 1];
array[j + 1] = array[j];
array[j] = tmp;
}
}
}
}
昇順や降順を変更したい時は、if文の中身の不等号を逆にするだけです。
次はクイックソートについて学んでいきます！
