Contents
- 構文
- 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
コムソート
コムソートは、ソートアルゴリズムの一つ。バブルソートの改良版でコームソートや櫛(くし)ソートともいわれます。
バブルソートでは直接隣接している2つの要素を比較交換していましたが、コムソートではソートの初期段階では離れた要素を比較交換します。そして徐々に2つの要素間の距離を縮めて、最後に直接隣接している要素どうしの比較交換を行います。そのため最後は普通にバブルソートを行っていることになります。
アルゴリズム
- 総数nを1.3で割り、小数点以下を切り捨てた数を間隔hとする。
- i=0とする。
- i番目とi+h番目を比べ、i+h番目が小さい場合入れ替える。
- i=i+1とし、i+h>nとなるまで手順3を繰り返す。
- hがすでに1になっている場合は入れ替えが発生しなくなるまで手順1~3を繰り返す。
- hを1.3で割り、小数点以下を切り捨てた数を新たに間隔hとし、操作を繰り返す。
この記事は役に立ちましたか?