- 構文
- heapSort( Var 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
//////////////////////////////////////////////////
// 【引数】
// 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
この記事は役に立ちましたか?