挿入ソート - やさしいデスマーチ

挿入ソート（Insertion Sort）は最も基本的なソートアルゴリズムです。

我々の普段の生活の中でも馴染み深いアルゴリズムで、トランプの手札の整列や麻雀の牌を整列をする時に自然と行っています。
我々の行う挿入ソートでは要素を１つづつ適切な位置に挿入していくだけですが、プログラムで記述するには複雑です。
何故ならば、トランプや麻雀牌の要素の数は高々20程度であり、カードのマークなどの視覚情報を頼りに最適なソートを行っているからです。
たとえば３・４・６と並んでいる箇所を見つけたらば、その間に５を入れて・・・といった感じです。
このような柔軟なアルゴリズムをコンピュータに実行させるのは困難である為、厳密な手順（時には効率が悪い）を考えなくてはなりません。

アルゴリズムの中でもソートは特にその効率が議論の対象となってきました。
何故ならば、使われる頻度も高く効率も要求されるからです。
結果として様々なソートアルゴリズムが発明されています。

我々は学者ではありませんから、個々のアルゴリズムに関して細かい議論は行いません。
しかし、個々のアルゴリズムを学ぶ事はプログラミングの訓練には最適です。

ソートの効率

ソートは単純がゆえに効率が要求されるアルゴリズムです
しかし、効率と言っても様々な効率がある為、簡単に整理しておきます。

計算量

ソートは大量のデータを並び替える為、計算量（実行効率）が重視されます。
計算量は極力小さい事が求められますが、元のデータがどのような状態であるかによって計算量が変わる事もしばしばあります。
例えば、完全に無作為な並びの場合、ある程度は整列されている場合、ほとんど整列されていて最後の方に幾つかの要素を追加した場合、逆順にソートしたい場合・・・など様々です。
これらの全ての状況で常に最高のパフォーマンスを持つアルゴリズムは残念ながらありませんが、平均計算量と最悪計算量を計る事で大まかな性能は測定できます。

平均計算量とは全ての並び（パターン）を想定したとして、平均的な計算量を割り出したものです。
平均計算量が優れているアルゴリズムはどんなパターンにも満遍なく速いでしょう。
それに対して最悪計算量とは全ての並び（パターン）を想定して、最悪の並び（パターン）の計算量です。
当然ながらどちらも優れているならば何も問題ありませんが、平均計算量だけで考えてはならないという事です。

外部記憶量

メモリ効率はソートを行う場合に重要な項目の１つです。
大量のデータを扱う為、完全にそのデータをコピーしてしまったならばメモリが２倍消費してしまいます。
余計なメモリを消費しない事も重要な要素です。

現代のソート

この50年ほどでコンピュータの性能は格段に上がりました。
数十年前にスーパーコンピューターと呼ばれ数千万もするような施設だったものが、数万円のポータブル家庭用ゲーム機の性能に負けるほどの進化です。
処理能力・メモリ容量・表現能力全てが進化しました。

この事を踏まえてソートの効率を考えると意外な事実が見えてきます。
計算量、すなわち処理の手数はコンピュータが進化した事の恩恵を相対的にしか受けていません。
つまり、計算量が優れているアルゴリズムはより速く処理できるようになり、劣っているアルゴリズムも同じように速く処理できるようになります。
これは相対的なものであり、アルゴリズムが同じであれば今も昔も優劣は変わりません。
あるとすれば、かつては使い物にならなかったほど処理効率が遅いアルゴリズムであっても、現代のマシンでは許容範囲となったという事です（かつて速かったアルゴリズムはもっと速くなったわけですが…）。

ところが、外部記憶容量、すなわちメモリに関しては絶対的な性能（容量）があがりました。
かつては数100バイトという限られたメモリ空間の中で如何にメモリを効率よく扱うかは時として実行効率よりも重要でした。
しかし、現代では携帯などの特殊な環境で無い限り、メモリを節約しなくてはならない環境は少なくなったと言えます。
したがって、現代のソートアルゴリズムを考える場合、メモリ消費は極端に悪くなければ無視しても良い要素と言えます。

InsertionSort

それでは挿入ソートクラスをみて行きましょう。

package example06;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class InsertionSort {
    
    // 要素を格納する集合
    private ArrayList bookList = new ArrayList();
    // コンストラクタ
    public InsertionSort() {}
    // 本を追加
    public void add(Book book)
    {
        bookList.add(book);
    }
    // 挿入ソート（価格でソートする）
    public void sort()
    {
        HashSet bookSet = new HashSet(bookList);
        bookList.clear();
        for (Iterator iter = bookSet.iterator(); iter.hasNext();)
        {
            Book book = (Book) iter.next();
            insert(book);
        }
    }
    // リストを前から繰り返して挿入する
    private void insert(Book newBook)
    {
        int index = 0;
        for (Iterator iter = bookList.iterator(); iter.hasNext(); )
        {
            Book book = (Book) iter.next();
            if(newBook.getPrice() <= book.getPrice()) 
            {
                break;
            }
            index++;
        }
        bookList.add(index, newBook);
    }
    
    // 一覧を文字列出力
    public String toString()
    {
        StringBuffer buf = new StringBuffer();
        for (Iterator iter = bookList.iterator(); iter.hasNext();)
        {
            Book book = (Book) iter.next();
            buf.append(book);
            buf.append("\n");
        }
        return buf.toString();
    }
}

実行の為のサンプルコードは次のようになります。

    InsertionSort sort = new InsertionSort();
    sort.add(new Book("Java入門", 1980));
    sort.add(new Book("Java入門(2)", 1980));
    sort.add(new Book("C言語入門", 2100));
    sort.add(new Book("C#入門", 2500));
    sort.add(new Book("易しいJava", 1500));
    sort.add(new Book("基礎から学ぶJava", 1500));
    sort.add(new Book("Servlet/JSP入門", 3100));
    sort.add(new Book("デザインパターン", 3400));
    
    sort.sort();
    System.out.println(sort);

InsertionSortクラス

InsertionSortクラスは挿入ソートを実現する為のクラスです。
インスタンス変数としてArrayListを保持し、Bookの追加メソッドとしてadd()を定義しています。
また、toString()メソッドでは全Bookの一覧を出力できるようにしました。

sort()メソッド

ソート処理が実行されると、内部で保持していたBookの一覧を別の器（HashSet）に格納しておきます。
ここで注意しておきたいのは、bookListに幾つインスタンスが格納されていようが、生成されるインスタンスはHashSet１つである事です。
今までbookListから参照されていたインスタンスがbookSetから参照されるようになったに過ぎません。

sort()メソッドではbookSetからbookを１つづつ取り出して、insert()メソッドを呼び出しています。

insert()メソッド

insert()メソッドでは引数で与えられたbookをbookListに追加しています。
ただし、追加する場所はbookのpriceで整理された場所です。

1個目のbookがinsertされた場合、Iteratorによる反復処理は行われません。
したがって0番目にbookは追加されます。
2個目のbookがinsertされた場合、Iteratorによる反復処理が１回だけ行われます。
この時、1個目のbookよりも値段が安いのであれば0番目に、高いならば1番目（後ろ）に追加されます。

このように1つinsertする毎に元のArrayListに戻されていくのですが、その時に価格が小さい順番に並べられているのです。