コムソート-状況をグラフで表示

説明

コムソートの状況を1回ごとに棒グラフで表示します。

コムソートはバブルソートの改良版です。バブルソートが遅いのは並べ替えるデータが移動するのに時間（ステップ）がかかるためです。バブルソートは並べ替えるデータが1つずつ（1ステップ）しか移動しないためて低速なので、移動するステップを大きくすれば、より速く並べ替えることができます。移動するステップは1.3ほどにするのが妥当です。

何かキーを押すと次の並べ替え（ソート）が実行されます。

Studioで試す

以下のリンクから Jasmine Tea でこのサンプルプログラムを Studio 画面で開いて実際に試すことができます。プログラムを実行したいときは、エディターの右下にある青色の「実行」ボタンを押してください。

Studio で開く

プログラム

// コムソート（状況をグラフで表示）
cls
print "何かキーを押すと次の処理に進みます"
d@=[70,2,45,35,90,14,56,81,22,10]
// ソートを実行
dataMax=10
sf=1.3
gap=dataMax
flag=-1
do while flag=-1 or gap>1
  call viewData d@
  gap=round(gap/sf-0.5,0)
  if gap<1 then
    gap=1
  end if
  flag=-1
  for i=0 to dataMax-1-gap
    j=i+gap
    if d@[i]>d@[j] then
      tmp=d@[i]
      d@[i]=d@[j]
      d@[j]=tmp
      flag=0
    end if
  next
  do while inkey$()=""
  loop
loop
call viewData d@
// 配列の内容を表示
procedure viewData d@
  cls 2
  for i=0 to 9
    box (i*20+250,250)-(i*20+15+250,250-d@[i]),7,8
  next
  print
end procedure

解説

2行目で画面を消去しています。

4行目で並べ替えるデータを配列に入れています。

11行目でデータ内容を表示するプロシージャを呼び出しています。

6行目で並べ替えるデータの数を変数に入れています。

7行目でデータを移動させるステップを変数に入れています。

8行目でデータを比較する間隔（ギャップ）を変数に入れています。初期値はデータ個数にしておきます。つまり最大値です。並べ替えるデータが末尾にある場合でも、これにより最初の段階で先頭に並び替えることができます。

9行目でデータの並べ替えが発生したかどうかを示すフラグ変数を用意します。-1ならデータの並べ替えが発生していることを示します。コムソートではデータの個数から並べ替える回数を決めることができないため、ソートが完了したかどうかを示すフラグを用意する必要があります。

10〜23行が繰り返し処理です。繰り返し条件としては並べ替えが発生しており、さらにデータを比較する間隔（ギャップ）が1より大きいことが条件になります。

11行目でデータを比較する間隔（ギャップ）を算出しています。-0.5としているのは小数点以下を切り捨てるためです。データを比較する間隔（ギャップ）は常に整数値である必要があります。これは配列の添字・参照番号・インデックスとして利用するためです。

12〜14行目ではデータを比較する間隔（ギャップ）が1未満になったら1に戻しています。

15行目でフラグに-1を入れ、並べ替え中であることにします。

16〜22行でデータの個数からデータを比較する間隔（ギャップ）を引いた数だけ繰り返します。

17行目で比較するデータの位置を計算しています。

18行目でデータを比較し必要であれば入れ替えます。入れ替えたら並べ替え中のフラグ変数に0を入れます。

棒グラフはプロシージャviewData内で行っています。cls 2として棒フラグを表示する前にグラフィック画面のみ消去しています。グラフィック画面を消去しないと、棒グラフが重ねって表示されてしまいます。