バブルソート

バブルソート（Bubble Sort）は隣り合った2つの要素を比較し順序を入れ替えるという処理を繰り返すことでソートを実現するアルゴリズムです。
その名の通り、泡のように大きな（小さな）要素が上に浮いてくるようなイメージとなります。
聞いただけでは「どうしてソートできるの？」と不思議に思うかもしれません。
まずは下の図をご覧ください。

単純化の為に整数のソートとしました。
１巡目の処理では、最初のペアからお互いを比較して、左側の値が大きいならば右側に…と繰り返してゆきます。
このように要素数−１回の比較と交換で、最も右側には最大の値が移動してくるのです。

２巡目でも同様に最初のペアからお互いを比較して交換する処理を繰り返します。
この時１巡目で最後の要素が最も大きくなっている為、最後の比較は行いません。
したがって要素数−２回の比較と交換で、右から２番目には２番目に大きな値が入ります。

これを順次繰り返していくと、次第に右側がソートされて行き、最後の２つを比較すればソートが実現できます。

BubbleSortクラス

それではJavaでBubbleSortを記述してみましょう。
これまでのソートと同様にAbstractSortを継承しています。

package example06;

import java.util.ArrayList;

public class BubbleSort extends AbstractSort
{
    // バブルソート
    public void sort()
    {
        for (int i = 0; i < bookList.size() - 1; i++) {
            bubbleSort(bookList, i);
        }
    }
    // 順次比較
    private void bubbleSort(ArrayList list, int count)
    {
       for (int i = 0; i < list.size() - 1 - count; i++)
       {
           Book left = (Book) list.get(i);
           Book right = (Book) list.get(i + 1);
           if(right.getPrice() < left.getPrice()) {
               swap(list, i);
           }
       }
    }
    // indexとindex+1を入れ替える
    private void swap(ArrayList list, int index)
    {
        Object obj = list.remove(index);
        list.add(index + 1, obj);
    }
}

最初のforループでは、ArrayListの要素数−１回のバブルソート処理を行っています。
この時何回目かと、対象のArrayListをbubbleSort()メソッドに渡しています。

bubbleSort()メソッドではArrayListの最初のペアから順番に価格の比較を行っています。
ここでcountとして受け取った数はすなわち右端にソートされた要素の数です。
処理を効率よく行うために、このペア比較は右端のソートされた要素には行いません。
もし、比較の結果が左側の方が大きいならばそれらの要素を交換させています。