Module/ヒープソート

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46

 
 
 
 
 
 
 
 
 
 
 
 
 
-
-
|
!
!
-
|
|
!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

// HSP開発Wiki
// Heap Sort for HSP3 v1.0
 
#module HeapSort
// 配列変数の入れ替え target(i1) ⇔ target(i2)（内部命令）
#deffunc hsExchange@HeapSort array target, int i1, int i2, local tmp
    tmp = target(i1) : target(i1) = target(i2) : target(i2) = tmp
    return
 
// startIndex以下の子要素のバランスを取る（内部命令）
#deffunc hsArgo@HeapSort array target, int startIndex, int endIndex, local tmp
    tmp = (startIndex + 1) * 2 - 1
    if tmp > endIndex : return
    if tmp + 1 <= endIndex {
        if ((target(tmp) < target(tmp + 1))&(sortMode == 0)) | ((target(tmp) > target(tmp + 1))&(sortMode == 1)) {
            tmp++
        }
    }
    if ((target(startIndex) < target(tmp))&(sortMode == 0)) | ((target(startIndex) > target(tmp))&(sortMode == 1)) {
        hsExchange target, startIndex, tmp
        hsArgo target, tmp, endIndex
    }
    return
 
// ヒープの作成（内部命令）
#deffunc hsMakeHeap@HeapSort array target, local i
    for i, length(target) / 2 - 1 , -1, -1
        hsArgo target, i, length(target) - 1
    next
    return
 
// ソートの実行
// p2が0ならば昇順
// 0以外ならば降順
#deffunc _hSort array target, int p2
    sortMode = p2 != 0
    hsMakeHeap target
    repeat length(target)
        hsExchange target, 0, length(target) - cnt - 1
        hsArgo target, 0, length(target) - cnt - 2
    loop
    return
 
// パラメータ省略用マクロ
#define global hSort(%1, %2=0) _hSort %1, %2
#global