heapSortヒープソート関数

本ページには広告が含まれています。

引数に指定された配列をヒープソートで並び替えます。

構文
heapSort( array )
引数
array 必須
ソートする数値を格納した配列。参照引数。
戻り値

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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

使い方

UWSC
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)\)

アルゴリズム

  1. 配列をヒープと呼ばれる完全二分木に変換します。
  2. ヒープから最大値(あるいは最小値)を取り出し、配列の最後の要素と交換します。
  3. 配列の最後の要素を除いた部分をヒープとして再構築します。
  4. 2と3の処理を、配列の最初の要素が最大値になるまで繰り返します。

関連記事

QSORT関数 (スクリプト関数)
QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
small関数 (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
bubbleSort関数 (自作関数)
引数に指定された配列を バブルソート で並び替えます。
shakerSort関数 (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
gnomeSort関数 (自作関数)
引数に指定された配列を ノームソート で並び替えます。
insertionSort関数 (自作関数)
引数に指定された配列を 挿入ソート で並び替えます。
shellSort関数 (自作関数)
引数に指定された配列を シェルソート で並び替えます。
quickSort関数 (自作関数)
引数に指定された配列を クイックソート で並び替えます。
shearSort関数 (自作関数)
引数に指定された配列を シェアソート で並び替えます。
Sort.Header プロパティ (Excel)
最初の行にヘッダー情報が含まれるかどうかを指定します。