選択ソート

選択ソート（Selection Sort）も基本的なソートアルゴリズムです。
挿入ソート（Insertion Sort）では、無作為に１要素づつ選び出し、適当な場所に挿入していく手順を踏みました。
これに対して選択ソートでは、最も小さい（大きい）要素から順に選び出し、順番に格納していく手順を踏みます。
したがって、処理の前半では大量のデータから最も小さい（大きい）要素を選び出す処理に時間が掛かりますが、処理が進むにつれて残っている要素が少なくなり比較は容易になっていく特徴があります。

SelectionSort

選択ソートをコードで表すと次のようになります。

package example06;

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

public class SelectionSort {
    
    // 要素を格納する集合
    private ArrayList bookList = new ArrayList();
    // コンストラクタ
    public SelectionSort() {}
    // 本を追加
    public void add(Book book)
    {
        bookList.add(book);
    }
    // 選択ソート（価格でソートする）
    public void sort()
    {
        HashSet bookSet = new HashSet(bookList);
        bookList.clear();
        while(bookSet.isEmpty() == false)
        {
            Book book = selectMinimunBook(bookSet);
            bookList.add(book);
            bookSet.remove(book);
        }
    }
    // 最も価格が小さい本をHashSetから選択して返す
    private Book selectMinimunBook(HashSet bookSet)
    {
        Book result = null;
        for (Iterator iter = bookSet.iterator(); iter.hasNext();)
        {
            Book book = (Book) iter.next();
            if(result == null || book.getPrice() <= result.getPrice()) {
                result = book;
            }
        }
        return result;
    }
}

実行時のサンプルは挿入ソートとほぼ同じです（実行クラスのみ修正）。

SelectionSort

このSelectionSortクラスはInsersionSortクラスと非常に良く似た構造となっています。
それもそのはずで、ソートのアルゴリズムは異なりますが、結果としてはソートを行うクラスを作ろうとしているので当然でしょう。
このように同じようなコードが複数のクラスに現れており、目的も似ているようであれば抽象クラスを定義する事で処理を共通化する事ができました。
この場合は次のように抽象クラスを定義できます。

package example06;

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

public abstract class AbstractSort
{
    // 要素を格納する集合
    ArrayList bookList = new ArrayList();
    // コンストラクタ
    public AbstractSort() {}
    // 本を追加
    public void add(Book book)
    {
        bookList.add(book);
    }
    // ソート
    public abstract void sort();
    // 一覧を文字列出力
    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();
    }
}

本の追加と文字列出力のメソッドを抽象クラスにそのまま移動しました。
それに伴い変数bookListも抽象クラスに移動しましたが、サブクラスで使用できるようにpackage privateのアクセスレベルにしています。
（privateのままにする場合は、getBookList()メソッドなどが必要となるでしょう）
この抽象クラスを継承してSelectionSortクラスを書き直せば次のようになります。

package example06;

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

public class SelectionSort extends AbstractSort {
    // コンストラクタ
    public SelectionSort() {}
    // 選択ソート（価格でソートする）
    public void sort()
    {
        HashSet bookSet = new HashSet(bookList);
        bookList.clear();
        while(bookSet.isEmpty() == false)
        {
            Book book = selectMinimunBook(bookSet);
            bookList.add(book);
            bookSet.remove(book);
        }
    }
    // 最も価格が小さい本をHashSetから選択して返す
    private Book selectMinimunBook(HashSet bookSet)
    {
        Book result = null;
        for (Iterator iter = bookSet.iterator(); iter.hasNext();)
        {
            Book book = (Book) iter.next();
            if(result == null || book.getPrice() <= result.getPrice()) {
                result = book;
            }
        }
        return result;
    }
}

また、sort()メソッドを抽象メソッドとして定義することで、実行のサンプルは次のように書くことができます。

    AbstractSort sort = new SelectionSort();
    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);

変数の型は抽象クラスですが、add()メソッドもsort()メソッドも抽象クラスに定義されているので問題ありません。
実際にsort()が呼び出された場合、実装クラスであるSelectionSortクラスの実装が実行されるわけです。
InsersionSortも同じように抽象クラスを継承する形に書き換えたならば、InsersionSortでソートを行いたい時には１行だけ修正する事で対応できます。

    AbstractSort sort = new InsersionSort();

sort()

ソート処理の中ではInsersionSortと同じように要素をHashSetに移した後、ArrayListをクリアしています。
続いてHashSetの中から最も価格の小さい要素を選択してArrayListに追加しHashSetからは取り除きます。
これをHashSetの要素がなくなるまで繰り返しています。

selectMinimunBook()

ここでは全ての要素の中から最も価格の小さい要素を選択するメソッドです。
これは線形検索のアルゴリズムの変形です。