Sortdemo はいろいろなソート (データの整列) のアルゴリズムを視覚的にデモするためのプログラムです。 右図のような画像データを、ソートアルゴリズムの各ステップについて作り出します。
作者: Anuradha Ratnaweera さん他
ホームページ:
http://www.lklug.pdn.ac.lk/software/sortdemo/
バージョン: 0.2 (2000/04/25)
ライセンス: GPL
付属ドキュメント README を読む
インストールしたら、 まず適当な作業ディレクトリを作ってそこへ移動しましょう。 Sortdemo は大量の画像データを作るからです。
$ mkdir work $ cd work
試しに次のコマンドを実行してみてください。
$ sortdemo quick random 20
これは quick sort のアルゴリズムで randam な 20
個のデータを用いた場合の画像データを作成する、という意味です。
実行が終わるとおよそ 100 〜 150 のファイルができるはずです。
ファイル unsorted.d にはソートする前のデータが、また
sorted.d にはソートした後のデータが記述されています。
画像データは sortXXXXX.png
(XXXXX は順序を示す番号) というファイルです。
では画像を見てみましょう。 複数の画像ファイルを順に見ることができるアプリケーションなら何でもよいのですが、 MLD 5,6 に標準インストールされている ImageMagick に含まれる display を使ってみます (MLD 7 では DVD-ROM から ImageMagick-5.4.7 を追加インストールしてください)。
$ display sort*.png
これで sort00000.png が表示されるはずです。
画像ウィンドウの中にマウスカーソルを持っていって、
スペースキーを押すごとに次の画像が表示されます。
比較の対象になっている２つのデータが緑色で示されています。 交換 (あるいは移動) されるステップでは対象は赤色で表示されます。 アルゴリズムによっては「注目していないデータ群」が灰色で示されます。
コマンド引数をなにも付けないで起動するとへルプが表示されます。
$ sortdemo usage: sortdemo type data size type: s, selection selection sort i, insertion insertion sort b1, bubble1 bubble sort b2, bubble2 bubble sort with a flag b3, bubble3 two way bubble sort (shaker sort) with a flag b4, bubble4 enhanced two way bubble sort with a flag q, quick quick sort data: s, sorted sorted re, reverse reverse ra, random random as, almost-sorted almost sorted ar, almost-reverse almost reverse size: size of the list
いろいろな組合わせを試してみてください。ただし、 sortdemo を実行する都度、別の (空の) 作業用ディレクトリに移るか、 または前にできたファイルをすべて消すのを忘れないようにしましょう。 またデータ数は 100 までできますが 多くすればそれだけ大量のファイルが作られますので気をつけてください。
ImageMagick の display についての詳細は man page を参照してください。
$ man display
LinuxMLD 7
では
sortdemo-0.2-1_mlb2.i386.rpm (16,059 bytes)
をインストールします。
rpm コマンドでインストールするにはスーパーユーザになって
# rpm -i sortdemo-0.2-1_mlb2.i386.rpm
とします。
MLD 5,6 では
sortdemo-0.2-1_mlb1.i386.rpm (15,548 bytes)
をインストールしてください。
※ MLD 7、MLD 6 では先に gd-1.8.4 を追加インストールしてください。
MLD 5,6 では Gnome の GUI でインストールすることもできます。
Web 上の参考になるページを御紹介します。