課題3

このプロジェクトを以下のように設定しよう。

最初に、タイトル、説明などを設定してプロジェクトを生成しよう。

コンピュータよりも、人間がソート（整列）を行う場合に近いアルゴリズムを紹介しよう。すでに紹介した、挿入法もよく人間が行うソートである。今回のソートでは、前処理として、（数字だったら）０〜９、１０〜１９、２０〜２９というようにその位であらかじめ分類し、その後、各グループ毎に挿入法などを用いてソートする方法である。このソート方法をバケツソートという。

例えは、以下の数字の並びがあるとしよう。

４、４７、７０、１３、４３、２３

[0] [1]   [2]  [3]   [4]  [5]

余分に値を格納する領域はないものとし、交換により、０〜９、１０〜１９などの位によりグループ化しよう。最初に、０〜９の間の値を左から探す。４([0])が見つかる。それと右側の値を交換するために、今度は、右から０〜９の間に「ない」値を探し、２３([5])が見つかる。４と２３を交換しよう。

２３、４７、７０、１３、４３、４

となる。さらに、４７([1])、７０([2])と０〜９の間にある値を探し、１３([3])まできたところでこれ以上ないことがわかる(もし、４３[4]が該当しても交換できない)。次に、１０〜１９の間の値を２３から（左から右へ）探し、１３があることがわかる。１３は、今度は、右の４３([4])から１０〜１９の間に「ない」値を探し、４３が見つかる。１３と４３を交換しよう。さらに、１０〜１９の値を探すがないことがわかるので次へ進む。

２３、４７、７０、４３、１３、４

今度は、２３（[0]）から４３（[3]）までに２０〜２９の間の値を探し、２３（[0]）が見つかる。右の４３（[4]）から２０〜２９の間に「ない」値を探す。４３が見つかる。２３と４３を交換しよう。

４３、４７、７０、２３、１３、４

４３（[0]）から７０（[2]）までに３０から４９の値を探し、該当する値がないことがわかる。さらに、４３から７０までに、４０〜４９の間の値を探し４３が見つかる。右の７０から４０〜４９に「ない」値を探し、７０が見つかる。４３と７０を交換する。

７０、４７、４３、２３、１３、４

同様に、４７がみつかるが右から検索する値も４７であるので交換はしない。

７０、４７、４３、２３、１３、４

５０〜５９の間の値、６０〜６９の間の値を探すが、該当する値がないことがわかる。７０〜７９の間の値についは、７０が見つかるが、右から検索する値がないので交換はしない。８０〜８９の間の値、９０〜９９の間の値についても該当する値がないことにより、上の並びが求める値の並びであることがわかる。

このアルゴリズムを以下に示す。以下で、i、j、count　を変数とし、N を定数とする。

1. N個の値を Array[0] 〜 Array[N-1]　に入力する。
2. i を 0、j を N-1、count を 0 とする。
3. Array[0] 〜 Array[j] まで、count 〜 count+9 の間にある値を探す。count が 210 であれば終了。
4. もし、見つからなければ 10 へ飛び越し
5. 最初に、見つかった値 Array[i] を A とし、Array[j] から j を減らす方向へ、count 〜 count+9 の間に「ない」値を探す。
6. もし、見つからなければ交換ぜずに、9 へ飛び越し
7. 最初に、見つかった値 Array[ｊ] を B とする。
8. もし、j > i が成り立っていれば交換する（Array[i]とArray[ｊ])。
9. 3　へ飛び越し、残りの配列を検索する。
10. count = count + 10 とし、3　へ飛び越し

以上のアルゴリズムをプログラムしよう。本課題では、０〜９、１０〜１９のような各位の中の値については、プログラムしない。他の挿入法などを使ってプログラムすればよい。

以下のようにボタンを配置する。

下部に、JPanel を定義するのを忘れないようにしよう。

最初に、import 文を追加しよう。

これまでのソートの問題と同様に、変数を宣言しよう。

さらに、これまでのソートの問題と同様に「初期化」ボタンに対するメソッドを定義する。

ここで、Draw( ) メソッドも同様に定義することができる。

すると、「初期化」ボタンをクリックすることにより以下のように実行することができる。

最初に、0 〜 9 の間の値を検索することを示している。

では、「整列」ボタンをクリックした場合のメソッドを記述しよう。

上のメソッドで呼び出す search( ) メソッドは以下のようになる。

プログラムを実行し、「初期化」ボタンをクリックした後、「整列」ボタンをクリックすると以下のようになる。