ヒープソート     Last modified: May 15, 2002
#heap_sort
# 配列 a[0] 〜 a[n-1] に n 個の数値データが入っているのを整列させる
# 使用例: heap_sort(n, a)

function heap_sort(n, a, i, j, k, x)
{
   for (k = int (n / 2) - 1; k >= 0; k--) {
       i = k
       x = a[i]
       while ((j = 2 * i + 1) < n) {
           if (j < n - 1 && a[j] < a[j + 1]) {
               j++
           }
           if (x >= a[j]) {
               break
           }
           a[i] = a[j]
           i = j
       }
       a[i] = x
   }
   while (n > 1) {
       n--
       x = a[n]
       a[n] = a[0]
       i = 0
       while ((j = 2 * i + 1) < n) {
           if (j < n - 1 && a[j] < a[j + 1]) {
               j++
           }
           if (x >= a[j]) {
               break
           }
           a[i] = a[j]
           i = j
       }
       a[i] = x
   }
}

・ 直前のページへ戻る  ・ E-mail to Shigenobu AOKI