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行目
DIM num = UBound(array)
- 3行目
DIM h = num
- 4行目
- 入れ替えが行われたかどうかを代入する変数。入れ替えが行われたらTrue。
DIM flg = FALSE
- 5,14行目
WHILE h > 1 OR flg … WEND
- 6行目
- 間隔hを1.3で割った値を新たな間隔とする。
IF h > 1 THEN h = INT(h / 1.3)
- 7行目
flg = FALSE
- 8-13行目
- 配列のn番目とn+h番目を比較し、n番目の方が大きければ入れ替える。
FOR n = 0 TO num - h IFB array[n] > array[n+h] THEN swap(array[n], array[n+h]) flg = TRUE ENDIF NEXT
コムソート
コムソートは、ソートアルゴリズムの一つ。バブルソートの改良版でコームソートや櫛くしソートともいわれます。
バブルソートでは直接隣接している２つの要素を比較交換していましたが、コムソートではソートの初期段階では離れた要素を比較交換します。そして徐々に２つの要素間の距離を縮めて、最後に直接隣接している要素どうしの比較交換を行います。そのため最後は普通にバブルソートを行っていることになります。
アルゴリズム
- 総数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とし、操作を繰り返す。
| 最悪計算時間 | \(\Omega(n^{2})\) |
|---|---|
| 最良計算時間 | \(O(n)\) |
| 平均計算時間 | \(\Omega(n^{2}/2^{p})\) pは増加数 |
関連記事
- QSORT (スクリプト関数)
- QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
- gnomeSort
- ノームソートはソートアルゴリズムの一つです。挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行います。
- heapSort
- 引数に指定された配列をヒープソートで並び替えます。
- bubbleSort
- 引数に指定した配列をバブルソートで並び替えます。
- shakerSort
- シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良したもの。双方向バブルソート、改良交換法とも言われます。バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行います。
- selectionSort
- 選択ソートは、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えを行うことでソートします。
- insertionSort
- 挿入ソートは、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入します。
- shellSort
- シェルソートは挿入ソートが改良された整列アルゴリズムです。リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行します。
- oddEvenSort
- 奇偶転置ソートは、ソートのアルゴリズムの一つで、バブルソートを改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行います。
- shearSort
- シェアソートはソートアルゴリズムの一つで、データを長方形に並べた上で各行・各列ごとにソートを行ないます。
- mergeSort
- マージソートは整列されていないリストを2つのリストに分割して、それぞれを整列させた後、それらをマージして整列済みのひとつのリストを作ります。
- quickSort
- 問題を小さな部分問題に分割していく分割統治法を利用した手法で、データから適当に基準値を決めこれより大きいグループと小さいグループに分けるという手順を、分けた小さなグループに対しても再帰的に繰り返していきます。
- bogoSort
- 要素をランダムに並べ替えることで偶発的な一致を試みる整列アルゴリズムです。
- Sort オブジェクト (Excel)
- データの並べ替えを表します。
- CALCARRAY (スクリプト関数)
- 配列の合計値・最小値・最大値・平均値を求めます。
- GETALLWIN (スクリプト関数)
- 全ウィンドウのIDを取得します。
- JOIN (スクリプト関数)
- 引数に指定した配列を結合し文字列を返します。
- POPUPMENU (スクリプト関数)
- ポップアップメニューを表示し、引数に指定した配列の中から選択された項目の要素番号を取得します。選択された項目を取得したい場合は、POPUPMENUの戻値を引数に指定した配列の要素番号として指定します。
- RESIZE (スクリプト関数)
- 配列のサイズを変更します。第二引数を省略した場合はサイズを取得します。
- SETCLEAR (スクリプト関数)
- 配列のすべての要素を任意の値で埋めます。
- SHIFTARRAY (スクリプト関数)
- 配列を指定した値だけシフトします。プラス値で後方、マイナス値で前方にシフトします。
- SLICE (スクリプト関数)
- SLICE関数は、配列の中を指定範囲の配列で返す関数です。第一引数に配列を指定し、第二引数に開始位置、第三引数に終了位置を指定します。第二・第三引数は省略可能で、省略した場合は配列全体を返します。戻値はsafearray型です。
- SPLIT (スクリプト関数)
- SPLIT関数は、引数に指定された文字列を区切文字列で区切り配列に格納します。区切文字列を省略した場合、スペースが区切文字列となります。戻値は配列でsafearray型です。
- UBound
- 配列の最大インデックスを返します。
- 連想配列
- 連想配列とは、自動的に割り当てられる数字をキーとして持つかわりに、自由に任意の文字列を割り振ることができる配列のことです。添え字に番号の変わりに名前をつけることでわかりやすく管理することができます。
- inArray
- divisors
- 引数に指定した数値の約数をリストを配列で返します。
- arraySearch
- 配列の中から指定した要素が見つかった場合、その要素がある最初のインデックスを返します。
- FOR-IN-NEXT
- 配列やコレクションなどのグループの各要素に対して繰り返し処理を行います。
- arrayReverse
- 引数に指定した配列を逆順にして返します。