アルゴリズムB 第4回



比較によらないソート(1)

今まで見てきた「キーの大小を比較して整列」するアルゴリズムは 計算量の下限が O(n log n) になることが理論的に 証明されています。

ところが、キーの大小を比較しない方法を使うとO(n)の計算時間で 整列が可能です。 ただし、キーがある条件を満していなければなりませんが。

ビンソート

「キーが整数で、ある範囲に収まっていて、重複がない」場合に ビンソートが使えます。 キーの取り得る値全てについてデータの記憶場所(bin、ビン)を確保し、 キーにしたがってデータをビンに入れていきます。 最後に、ビンを前から順に集めれば、昇べきの順でデータを整列したことになります。 (p.381, Fig.17.1)

BinSortData.java
授業で配布するプリントを参照して下さい。
BinSort.java
授業で配布するプリントを参照して下さい。
RunBinSort.java
授業で配布するプリントを参照して下さい。
RunBinSort.javaの実行例
$ javac RunBinSort.java
$ java RunBinSort
{13:要素0 24:要素1 15:要素2 5:要素3 98:要素4 44:要素5 35:要素6 96:要素7 
 82:要素8 73:要素9 }                    ←元のデータ(本来は1行で表示)
{5:要素3 13:要素0 15:要素2 24:要素1 35:要素6 44:要素5 73:要素9 82:要素8 
 96:要素7 98:要素4 }                    ←整列済みのデータ(本来は1行で表示)

データの個数をn, 用意したビンの個数をmとすると、

  n個のデータをビンに振り分ける手間は O(n)
  データをビンから取り出す手間は O(m)
となるので、これらを合計して、
  ビンソートの計算量はO(n+m)
となります。mがnに比べて極端に大きくなければ m はnと同程度 (少なくとも定数倍)とみなされるので
  ビンソートの計算量はO(n)
となります。

分布数え上げソート

ビンソートにおける「重複したデータがない」という条件を緩めて、 「重複したデータがあっても構わない」としたソートが 「分布数え上げソート」です。

p.390 Table17.1
データ: 7, 1, 4, 2, 7, 8, 2
キー k出現回数 a累計 b
000
111
223
303
414
504
604
726
817
907
1007

累計[i]は、キーが0〜iの間にあるデータの個数となります。 データの置き場所として、0番目から数えているので、 キーが i のデータは (累計[i-1])番目 または(累計[i] - 1)番目に 配置すればよいわけです。

教科書では、キーが0の場合でも特別扱いが必要ない 「(累計[i] - 1)番目に配置する」方式をとっています。

データを配置する度に 「累計[i] = 累計[i] - 1」とすれば キーの値が同じ複数のデータがあってもうまく配置できます。 ただし、この場合、キーの値が同じデータは「後ろから前へ」と 並べられることになりますので、 ソートしたデータが「安定である(=同じキーの値を持つデータ同士では、 元の順序関係がソート後の順序でも保持される)」ためには、 元のデータが後にあったものから配置する必要があります。

DistributionCountingSort.java
授業で配布するプリントを参照して下さい。

RunDistributionCountingSort.java
授業で配布するプリントを参照して下さい。
RunDistributionCountingSort.javaの実行例
$ javac RunDistributionCountingSort.java
$ java RunDistributionCountingSort
{13:要素0 24:要素1 15:要素2 5:要素3 98:要素4 44:要素5 35:要素6 15:要素7
 82:要素8 73:要素9 }               ←元のデータ(本来は1行で表示)
{5:要素3 13:要素0 15:要素2 15:要素7 24:要素1 35:要素6 44:要素5 73:要素9
 82:要素8 98:要素4 }               ←整列済みのデータ(本来は1行で表示)

データの個数をn, 分布表の要素数をmとすると、

  分布表を用意する O(m)
  データのキーの分布を調べる O(n)
  キーの累積度数分布を求める O(m)
  度数分布にしたがってデータを配置する O(n)
  (ソートしたデータを元の配列に書き戻す   O(n))
となり、全体の計算量は O(n+m) となります。 mがnに比べて極端に大きくなければ(定数倍程度ならば)、 計算量はO(n)とみなせます。 もしmがnに比べて極端に大きければO(m)とみなせます。



アルゴリズムB 演習


作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを http://nw.tsuda.ac.jp/class/algoB/local/handin/ で必ず確認しておいて下さい。

課題提出〆切は次回の講義開始時刻です。

課題4a: BinSortのプログラムを動かしてみよう

提出ファイルBinSort.java
コメント欄:RunBinSort.javaに例と同じデータを与えた時の出力
提出先: 「宿題提出Web:アルゴリズムB:課題4a」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai4a

上記の BinSortData.java, BinSort.java, RunBinSort.java を自分で入力し、 動作させてみましょう。 動作を確実に理解して下さい。

課題4b: 分布数え上げソートのプログラムを動かしてみよう

提出ファイルRunDistributionCountingSort2.java
コメント欄:分布数え上げソートがrand400k.txt, inc400k.txt, dec400k.txtをそれぞれソートするのにかかる時間
提出先: 「宿題提出Web:アルゴリズムB:課題4b」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai4b

課題2で使った http://nw.tsuda.ac.jp/class/algoB/sortdata/の下の 3種類のデータ

は、データの最小値が0で、最大値が 999999であることが保証されています。

RunDistributionCountingSort.java を参考にして、 標準入力から上記のデータを読み込んでソートする RunDistributionCountingSort2.javaを作りなさい。

さらに、DistributionCountingSort2.javaが、rand400k.txt, inc400k.txt, dec400k.txtを読み込んでソートするのに必要な時間を それぞれ計測し、答えなさい。 結果の出力にかかる時間を含めたくないので、実行時間を計測する場合は ソートし終わった状態を標準出力に表示するコードをコメントアウトしてから 測るのが望ましい。

[注意] DistributionCountingSortクラスは BinSortDataオブジェクトの 配列をソートしますが、今回扱うデータは整数値のみです。 そこで、データをkeyフィールドに保存し、dataフィールドには keyと同じ値のIntegerオブジェクトを入れておけばよいものとします。

課題4c: ビンソートの応用

提出ファイルRunBinSort2.java
コメント欄:(最小のデータを0番目と表現する数え方で)小さい方から 5番目と10番目のデータ
入力ファイルは次の2種類。
http://nw.tsuda.ac.jp/class/algoB/bindata01.txt
http://nw.tsuda.ac.jp/class/algoB/bindata02.txt
提出先: 「宿題提出Web:アルゴリズムB:課題4c」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai4c

複数の整数値がデータとして与えられる。 データに重複した値を持つものはなく、さらにデータの最小値と 最大値の差は100000以下であるものとする。

BinSort.javaを用いて、入力されたデータを小さい順に並べ替えて 指定された順番のデータを表示するRunBinSort2.javaを作成しなさい。

入力データ形式は次の通り。

  N
  D1
  D2
  ...
  DN

Nはデータの個数である。 Diはデータで整数値である。

    11 ≦ N ≦ 100000
    -1000000000 ≦ Di ≦ 1000000000
    0 ≦ max(Di)-min(Di) ≦ 100000
RunBinSort2.javaの実行例
授業で配布するプリントを参照して下さい。

[注意] BinSortクラスは BinSortDataオブジェクトの配列をソートしますが、 課題4a, 4b では扱うデータは整数値のみです。 そのような場合は、データをkeyフィールドに保存し、dataフィールドにはkeyと同じ値の Integerオブジェクトを入れておけばよいものとします。 課題4cではデータから最小値を引いたものをキーとして使い、元のデータはdataフィールドへ しまっておけばよいでしょう。