UWSC辞典

構文

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