ソフトの砂場(ソート)

最終更新日:1999/02/28

最近,ふとアルゴリズムの本(残念ながら,書名は失念)を立ち読みしていると, ソートの説明でデータが並んでいく様子を表す図を見かけました. 調べてみると,文献[2]にも同じような図があり,最近の流行かもしれません. ちょっと興味を持ったので作ってみました.実際に動かしてみると, 結構面白いものです.

sort実行例

ランダムデータの生成

ソートするデータとして,昇順,降順,ランダムの3種類を用意します. 昇順と降順データの生成は簡単ですが,ランダムデータをどのように 生成するかについて考えてみました.ここでは,まず昇順のデータを 用意しておき,その中の任意の二つを入れ替える操作を繰り返して, できたものをランダムデータとしました.

問題は,入れ替えをどの程度行えば十分に攪拌されるか,ということです. そこで,これも実際にプログラムを作成して,確認することにしました. プログラムを実行すると,画面右上がりの線が表示され,時間とともに 崩れていきます.下図はプログラムを実行して100回程度入れ替えを行った 後の状態を表します.この横軸には配列を添え字順にとり,縦軸には それぞれの値を表します.初期値として配列に昇順のデータを入れているので 実行直後は右上がりの線になり,入れ替えを行っていくとこの線は崩れて いきます.右下の繰り返し回数は,入れ替えを何回繰り返して行ったかを 表します.

実際にプログラムで試してみると,この300個のデータ であれば600回くらいで良いようです.以下のソートプログラムでは, 念の為に900回入れ替えを行っています.

ランダムデータの生成

各種ソート

ここでは,下に示すアルゴリズムに基づくソートプログラムを作成しました. 使い方は簡単で,起動してアルゴリズムとデータの初期値を選択し, あとはソートを実行して,ボーっと眺めるだけです(^_^). このプログラムはソートが行われる様子を見るのが目的なので,画面を更新する タイミングはアルゴリズムによって異なります.したがって,このプログラムを 見て,どのアルゴリズムが速いかなどの判断はしないでくださいね(しないと思いますが).

プログラムのダウンロード

このプログラムでは,ソートするデータを配列に入れておき,ソートされていく 時の配列内の様子を画面に表示しています.横軸には配列のインデックスをとり, 縦軸にはそれぞれの値をとっています.したがって,画面左端の点は,配列の インデックスが最小値の値を表し,その右はインデックスが2番目に小さい 配列の値を表し,と続き,一番右はインデックスが最大の配列の値を 表します.

配列内にデータが昇順に並んでいれば,点列は右上がりになり, 降順に並んでいれば点列は右下がりになります.配列内が並んでいなければ, 点列もバラバラになります.データを昇順にソートするので,ソートの結果 最終的には右上がりの点列が出来上がります.

実装したアルゴリズムと感想

単純挿入法
手でソートする時によく使うアルゴリズムでも,メモリ上ではこんな風に なっています.効率悪いですね.
単純選択法
動きが小さいので,あまり楽しくありません(目的が違う ^^;)
バブルソート
動きが大きいので見た目には楽しいのですが,どう考えても効率悪いです. 小さいデータは速く動くので画面右下のデータはだいたい昇順に並びますが, 大きいデータは1ステップずつしか動かないので画面上方のデータはバラバラです (この画面の最初の図を参照).動作の詳細は,バブルソート詳細版を動かして みればよくわかります.が,あまりにも遅いので,最後まで見ないと思うんですけど.
シェーカーソート
バブルソートを双方向に行うので,データの並び方もそのようになります. バブルソートよりは速いようですが,元が元だけに・・・
シェルソート
私はシェルソートとは,バブルソートの比較する間隔を広げたものであると, 勘違いしていました.このアルゴリズムの振る舞いは,データの初期値として 逆順を選ぶとよく分かります.
ヒープソート
私にとって,頭では分かっているつもりなのだが,納得いかない アルゴリズムの典型例です.ヒープを作る段階でだいたい降順にデータが並ぶので, 配列の最初に格納される根に最大値が入り,配列の最後のほうに格納される葉には 小さい値が入っているような気がします. しかし,この表示はヒープを表現するには向いていないので,よくわかりませんね.
クイックソート
画面再描画を頻繁に行っているので,全然クイックではありません. ランダムデータを初期値として与えると,分割統治型アルゴリズムらしい 振る舞いをします.

雑感

初めは,かすかな記憶を基に実装していましたが,アルゴリズムの本を見ると あまりにも処理内容が異なっていて(シェルソートなど)愕然としました. 動作状態が目に見えるので,変なアルゴリズムでも, それはそれで楽しめましたが・・・.

改造

 ソート中に、メモリのどのあたりのデータを比較、交換しているかを表示するようにしてみました。上の図で、緑の表示は比較、赤の表示は交換を表し、色が明るいほど最近比較、交換したことを表します。

 単純なアルゴリズムでは、常に広い範囲のデータの比較、交換を行っているのに対し、高度なアルゴリズムでは限定された範囲のデータの比較、交換を行っていることが分かります。

参考文献

  1. Wirth, N., アルゴリズム+データ構造=プログラム, 日本コンピュータ協会, 1979
  2. Sedgewick, R., アルゴリズム C++, 近代科学社, 1994

ホーム