sortdemo

Sortdemo

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 が表示されるはずです。 画像ウィンドウの中にマウスカーソルを持っていって、 スペースキーを押すごとに次の画像が表示されます。

sort00000 sort00001

比較の対象になっている2つのデータが緑色で示されています。 交換 (あるいは移動) されるステップでは対象は赤色で表示されます。 アルゴリズムによっては「注目していないデータ群」が灰色で示されます。

コマンド引数をなにも付けないで起動するとへルプが表示されます。

$ 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 上の参考になるページを御紹介します。

[2001/06/07 作成] [2003/10/30 更新]


このページに関する御意見、御要望を science@mlb.co.jp までお寄せ下さい
Copyright © 2001-2005 Media Lab. All Rights Reserved.