HSP教室 入門編

その19 バブルソート

	;バブルソートのサンプル
	dim data,100
;	       0  1  2 3 4  5 6 7 8  9 
	data.0=50,51,8,7,14,6,4,15,3,1
	n=10	;データ個数
	repeat n-1
		nct=cnt
		repeat n-nct-1
			j=cnt
			ne=j+1
			if (data.j <= data.ne):goto *nos
	;swap
			tmp=data.j	;ne=i+1
			data.j=data.ne:data.ne=tmp
*nos
	str aa
	loop
	aa=">>"+data.0+" "+data.1+" "+data.2+" "+data.3+" "+data.4
	aa=aa+" "+" "+data.5+" "+data.6+" "+data.7+" "+data.8+" "+data.9
	mes aa
	loop
;owari
	aa="--"+data.0+" "+data.1+" "+data.2+" "+data.3+" "+data.4
	aa=aa+" "+data.5+" "+data.6+" "+data.7+" "+data.8+" "+data.9
	mes aa
	stop
 

今回はソートです。
日本語で言うと、並べ替えです。
で、実際は住所録などを名前順に並べて、とかある程度まとまったデータのある部分を見てソートする事になるので、サンプルのプログラムよりも難しくなると思います。
hspda.dllにはsortnote命令などのnotepad形式のデータをソートする命令がありますが、
今回は標準の命令だけでソートを行います。
sortnote命令でのソートは「ゲームの得点を保存しよう!」に解説があります。

基本を押さえるということで、一番基本的な数だけを入れ替えるサンプルを作りました。
今回使った方法は、数あるソートアルゴリズムの中でも一番有名なバブルソートです。
データの形式や個数によっては向かない事も有るかもしれませんが、基本としてマスターしておきましょう。
では、数列の変化の様子を解説していきます。

元はこれです。
>>50 51 8 7 14 6 4 15 3 1
最初の比較で、50と51を比べる、これは入れかえなし。
次に51と8を比べる。
>>50 51 8 7 14 6 4 15 3 1
これは入れ替える。
それを最後までやると、51は一番右に行く。
>>50 8 7 14 6 4 15 3 1 51
1度の処理で、1番大きい値が右に行く。
次のループでは、最大の数51は除外して、同じ処理をする。

>>50 8 7 14 6 4 15 3 1 51
今度は50がぐんぐんあがっていきます。
>>8 7 14 6 4 15 3 1 50 51
で、右から2番目に落ち着く。

次の処理では、右端の2つ、50と51は除外して、左から処理を始めます。
>>7 8 6 4 14 3 1 15 50 51
今回の処理では、15が右にずれていきました。

同じ要領で繰り返すと、要素の数が減っていきます。
>>7 6 4 8 3 1 14 15 50 51
>>6 4 7 3 1 8 14 15 50 51
>>4 6 3 1 7 8 14 15 50 51
>>4 3 1 6 7 8 14 15 50 51
>>3 1 4 6 7 8 14 15 50 51
>>1 3 4 6 7 8 14 15 50 51

右から順番が決まっていく様子が分かったでしょうか?
この、大きい値が泡のように上っていく様子から、バブルソートと名づけられました。

bsort.asをダウンロード。

その20に行く

目次に戻る