combSort

タグ: ,
構文
combSort( Var array[] )
引数
array
ソートする数値を格納した配列。参照引数。
戻値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE combSort(Var array[])
	DIM num = UBound(array)
	DIM h = num
	DIM flg = FALSE
	WHILE h > 1 OR flg
		IF h > 1 THEN h = INT(h / 1.3)
		flg = FALSE
		FOR n = 0 TO num - h
			IFB array[n] > array[n+h] THEN
				swap(array[n], array[n+h])
				flg = TRUE
			ENDIF
		NEXT
	WEND
FEND

//////////////////////////////////////////////////
// 【引数】
//   a : 変数bと交換する値。参照引数。 
//   b : 変数aと交換する値。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND

コムソート

コムソートは、ソートアルゴリズムの一つ。バブルソートの改良版でコームソートや櫛（くし）ソートともいわれます。

バブルソートでは直接隣接している２つの要素を比較交換していましたが、コムソートではソートの初期段階では離れた要素を比較交換します。そして徐々に２つの要素間の距離を縮めて、最後に直接隣接している要素どうしの比較交換を行います。そのため最後は普通にバブルソートを行っていることになります。

アルゴリズム

  1. 総数nを1.3で割り、小数点以下を切り捨てた数を間隔hとする。
  2. i=0とする。
  3. i番目とi+h番目を比べ、i+h番目が小さい場合入れ替える。
  4. i=i+1とし、i+h>nとなるまで手順3を繰り返す。
  5. hがすでに1になっている場合は入れ替えが発生しなくなるまで手順1～3を繰り返す。
  6. hを1.3で割り、小数点以下を切り捨てた数を新たに間隔hとし、操作を繰り返す。