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

コムソート

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

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

アルゴリズム

  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とし、操作を繰り返す。