本ページには広告が含まれています。
引数に指定された配列をヒープソートで並び替えます。
- 構文
- heapSort( array )
- 引数
- array 必須
- ソートする数値を格納した配列。参照引数。
- 戻り値
プログラム
//////////////////////////////////////////////////
// 【引数】
// array : ソートする数値を格納した配列。参照引数。
// 【戻り値】
//
//////////////////////////////////////////////////
PROCEDURE heapSort(Var array[])
DIM i = 0
DIM u = UBound(array)
WHILE i < u
upHeap(array, i)
i = i + 1
WEND
WHILE i > 0
swap(array[0], array[i])
downHeap(array, i)
i = i - 1
WEND
FEND
PROCEDURE upHeap(Var array[], n)
WHILE n > 0
DIM parent = (n - 1) / 2
IFB array[parent] < array[n] THEN
swap(array[parent], array[n])
ELSE
BREAK
ENDIF
n = parent
WEND
FEND
PROCEDURE downHeap(Var array[], n)
DIM m = 0
DIM tmp = 0
WHILE TRUE
DIM LtChild = (m + 1) * 2 - 1
DIM RtChild = (m + 1) * 2
IF LtChild >= n THEN BREAK
IF array[LtChild] > array[tmp] THEN tmp = LtChild
IF RtChild < n AND array[RtChild] > array[tmp] THEN tmp = RtChild
IF tmp = m THEN BREAK
swap(array[tmp], array[m])
m = tmp
WEND
FEND
//////////////////////////////////////////////////
// 【引数】
// inputs : 繰り返す文字列
// multiplier : inputsを繰り返す回数
// 【戻り値】
//
//////////////////////////////////////////////////
FUNCTION strRepeat(inputs, multiplier)
DIM res = ""
FOR n = 1 TO multiplier
res = res + inputs
NEXT
RESULT = res
FEND
//////////////////////////////////////////////////
// 【引数】
// a : bと交換する値。参照引数。
// b : aと交換する値。参照引数。
// 【戻り値】
//
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
DIM tmp = a
a = b
b = tmp
FEND
//////////////////////////////////////////////////
// 【引数】
// arrayname : 上限値を求める配列の名前
// dimension : 返す次元を示す整数
// 【戻り値】
//
//////////////////////////////////////////////////
FUNCTION UBound(arrayname[], dimension = 1)
RESULT = EVAL("RESIZE(arrayname" + strRepeat("[0]", dimension - 1) + ")")
FEND
使い方
DIM array[] = 8, 20, 2, 22, 17, 30, 14, 4, 25, 5
heapSort(array)
FOR item IN array
PRINT item
NEXT
- 結果
2 4 5 8 14 17 20 22 25 30
ヒープソート
ヒープソート(Heap Sort)は、完全二分木というデータ構造を使って配列をソートするアルゴリズムです。ヒープソートは選択ソートの改良版とも言われています。
最悪計算時間 | \(O(n \log n)\) |
---|---|
最良計算時間 | \(\Omega(n)\) |
平均計算時間 | \(O(n \log n)\) |
アルゴリズム
- 配列をヒープと呼ばれる完全二分木に変換します。
- ヒープから最大値(あるいは最小値)を取り出し、配列の最後の要素と交換します。
- 配列の最後の要素を除いた部分をヒープとして再構築します。
- 2と3の処理を、配列の最初の要素が最大値になるまで繰り返します。
関連記事
- QSORT関数 (スクリプト関数)
- QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
- small関数 (自作関数)
- 配列の中で小さい方から数えた順位の値を求めます。
- bubbleSort関数 (自作関数)
- 引数に指定された配列を バブルソート で並び替えます。
- shakerSort関数 (自作関数)
- 引数に指定された配列を シェーカーソート で並び替えます。
- gnomeSort関数 (自作関数)
- 引数に指定された配列を ノームソート で並び替えます。
- insertionSort関数 (自作関数)
- 引数に指定された配列を 挿入ソート で並び替えます。
- shellSort関数 (自作関数)
- 引数に指定された配列を シェルソート で並び替えます。
- quickSort関数 (自作関数)
- 引数に指定された配列を クイックソート で並び替えます。
- shearSort関数 (自作関数)
- 引数に指定された配列を シェアソート で並び替えます。
- Sort.Header プロパティ (Excel)
- 最初の行にヘッダー情報が含まれるかどうかを指定します。