バブルソート (Bubble Sort)
今日も簡単なアルゴリズムのエントリーです。
私が初めて覚えたソートアルゴリズムです。
当時はこれを考えた人はもの凄い頭のいい人だと感動しました。
バブルソート (Bubble Sort) は読んで字のごとく泡のソートです。(^_^;)
つまりソートの過程がデータが下から上へ移動する様子が、泡が浮かんでいくように見えることから名付けられたとされています。
最悪計算時間が O(n2) と遅いのですがシンプルで理解しやすい優しいアルゴリズムです。
そして安定であることが特徴の一つでもあります。
実際どんなことをしているかというと隣り合う要素の大きさを比較して並べ替えていくという単純なものです。
これを要素数 –1 回繰り返すことでソートを行なうことによって完了します。
バブルソートのアルゴリズムを解説したサイトは数多く存在します。
たいていの場合は「要素数-1回繰り返すことでソートを行う」を素直にコードにして紹介されています。
これはバブルソートの解説には解りやすくて良いのですが無駄が発生するので良くありません。
なので今回、私は涙ぐましい改良を施されたバブルソートを組みました。
ソートの部分的完了を検出し、比較範囲の限定を行っています。
ついでに配列が並び変わっていく様子を表示させてみました。（比較、交換作業は除く）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
package jp.yucchi.bubblesort; import java.security.SecureRandom; import java.util.Arrays; /** * * @author Yucchi */ public class BubbleSort { 1 /** * @param args the command line arguments */ public static void main(String[] args) { int[] randomNumber = new SecureRandom().ints(10L, 1, 11).toArray(); System.out.println("befor:" + Arrays.toString(randomNumber) + System.getProperty("line.separator")); bubbleSort(randomNumber); System.out.println(System.getProperty("line.separator") + "after:" + Arrays.toString(randomNumber)); } private static void bubbleSort(int[] randomNumber) { int incompleteIndex = 0; // ソートがまだ完了していない位置 while (incompleteIndex < randomNumber.length - 1) { int lastChangeIndex = randomNumber.length - 1; // 最後に要素を交換した位置 for (int j = randomNumber.length - 1; j > incompleteIndex; j--) { if (randomNumber[j - 1] > randomNumber[j]) { // 要素の交換 本当は一時変数を用意して入れ替えるのが良い randomNumber[j - 1] ^= randomNumber[j]; randomNumber[j] ^= randomNumber[j - 1]; randomNumber[j - 1] ^= randomNumber[j]; lastChangeIndex = j; } } incompleteIndex = lastChangeIndex; trace(randomNumber); } } private static void trace(int[] randomNumber) { System.out.println("trace:" + Arrays.toString(randomNumber)); } } |
プログラムの実行結果は下図のようになります。
ザックリ説明すると例えば次のような配列が与えられた時
1, 2, 5, 8, 7, 9, 6
最初の while ループは
1, 2, 5, 8, 7, 9 ← 6
1, 2, 5, 8, 7 ← 6, 9
1, 2, 5, 8 ← 6, 7, 9
1, 2, 5 – 6, 8, 7, 9
1, 2 – 5, 6, 8, 7, 9
1 – 2, 5, 6, 8, 7, 9 （赤字は比較交換、緑字は比較未交換）
となり、配列のインデクスナンバー 3 まではソート完了となります。
1, 2, 5, 6, 8, 7, 9 (ピンク色の数字はソート完了済み）
よって、while ループの条件を可変することにより無駄な処理をへらせます。
また、内側の for ループも最後に要素交換した右側のインデックスナンバー（ソートが確定していない）を利用して
無駄に比較捜査をしないようにさせています。要するにソート済み部分の再捜査をしないことによって効率を上げようというものです。
次の while ループ処理は
1, 2, 5, 6, 8, 7 – 9
1, 2, 5, 6, 8 ← 7, 9
1, 2, 5, 6, 7, 8, 9
次の While ループで
1, 2, 5, 6, 7, 8 – 9
1, 2, 5, 6, 7, 8, 9
ソート完了！
もし、涙ぐましい改良がされていなければ無駄な比較処理がたくさん行われることになったでしょう。
今回は一般的なバブルソートの改良版を紹介しましたがバブルソートの亜種はまだあります。
シェーカーソートはバブルソートの亜種で安定のまま高効率化が達成？されています。
これはバブルソートを先頭からと末尾から交互に捜査して並べ替えていくものです。
だからシェーカーなんですね。(^_^)
アルゴリズムの基本的な考え方はバブルソートそのものなので興味のあるかたはプログラムを組んで楽しんでください。(^_^)
TAGS: Java | 2015年2月6日2:15 PM
Trackback URL