ソーティングアルゴリズム(2/5)

昨年（令和2年）の電検三種の機械科目で、ソーティングの問題が出た。
問題は、ｎ個の配列の数値を大きい順（降順）に並べ替えるプログラムのフローチャートの穴埋め問題。既知の並べ替えのアルゴリズムはあるだろうが、自分で考えて試行錯誤してようやくできた。

その後、ネットでアルゴリズムを調べると、このプログラムはバブルソートというのだそうだ。隣り合うふたつの要素の値を比較して、条件に応じた交換を行い整列させていく方法である。並べ替えの過程でデータが下から上へ移動する様子が泡が浮かんでいくように見えることからこの名前がついているとのこと。なるほど・・・。
最近の高級言語は、ソート関数（命令）があるので何も考えずに使っているが、こうした基本のアルゴリズムを理解しておくと、プログラム作成に役立つと感じた。

ソートプログラム（awk)：

BEGIN{
	FS=OFS=","
}

### data.txt --> 3,1,2,5,4のCSV形式データを準備
### data.txtの読み込み
{ split($0,a) 
	for(i=1;i<6;i++) {
		printf(a[i]",")
	}
  print ""
}

### END文　ソーティング
END{
 num=0 #比較ループの回数カウント
 for(i=1;i<6; i++) {
	for(j=i+1;j<6; j++) {
		if(a[i]<a[j] ){		#a[i]が小さいなら
			m=a[i]			    #a[i],a[j]を入れ替える
			a[i]=a[j]		
			a[j]=m			
			num ++
		}
	}		
 }

 # ソート結果の出力
 printf("a[i]=")
 for(i=1;i<6;i++) {
	printf(a[i]",")
 }
 # 比較ループの回数
 print""
 print "num="num
}

出力結果：

>gawk -f sort.awk data.txt
3,1,2,5,4,
a[i]=5,4,3,2,1,
num=7

if(a[i]<a[j] )　⇒　if(a[i]>a[j] )とすると、昇順ソートになる。