heapSort

構文
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