ヒープソート(再帰的でない)

概要
前の記事では、スタックソートの再帰アルゴリズムについて説明しましたが、再帰アルゴリズムは非再帰演算に比べて主に以下の利点があります.

は、元の問題をより小規模なサブ問題(分治法)に分類する.

コード構造が明確で、コード量が少なく、可読性が強い.

しかし、再帰的には次のような欠点もあります.

は関数を再帰的に呼び出し、時間のオーバーヘッドが大きい.

再帰が深すぎてスタックオーバーフローを招きやすい.

上記の2つの欠点を解決するために,本論文では,非再帰的に非再帰的なバージョンを実現するスタックソートアルゴリズムを採用した.しかし,非再帰版のスタックソートアルゴリズムは,関数の呼び出し回数を減らし,スタックオーバーフローの可能性を回避するが,そのコードは比較的複雑で理解しにくいことに注意すべきである.
ヒープソート実装(非再帰版)

#include <stdio.h>

#define LEFT(i)     (((i) << 1) + 1)
#define RIGHT(i)    (((i) << 1) + 2)
#define PARENT(i)   (((i) - 1) >> 1)

void heap_sort(int *A, int len)
{
  int l, r, largest;
  int i, j, tmp;

  i = PARENT(len - 1); /* Get the last non-leaf node */

  while (i >= 0) { /* Build the heap */
    l = LEFT(i);
    r = RIGHT(i);

    largest = i;
    if (l < len && A[l] > A[largest]) {
      largest = l;
    }
    if (r < len && A[r] > A[largest]) {
      largest = r;
    }

    if (largest != i) {
      tmp = A[i];
      A[i] = A[largest];
      A[largest] = tmp;
      i = largest;
    } else {
      i--;
    }
  }

  len--;
  while (len > 0) {
    tmp = A[0];          /* Sort */
    A[0] = A[len];
    A[len] = tmp;

    len--;
    i = 0;
    while (1) {         /* Heapify */
      l = LEFT(i);
      r = RIGHT(i);

      if (l < len && A[l] > A[largest]) {
        largest = l;
      }

      if (r < len && A[r] > A[largest]) {
        largest = r;
      }

      if (largest != i) {
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      } else {
        break;
      }
    }
  }
}

void display(int *A, int len)
{
  int i;

  for (i = 0; i < len; i++) {
    printf("%d ", A[i]);
  }
  printf("
");
}

int main()
{
  int A[] = {10, 32, 43, 31, 2, 45, 12, 9, 71, 41, 10, -19, 32, 4, 8, 6};
  int len = sizeof(A) / sizeof(A[0]);

  display(A, len);

  heap_sort(A, len);

  display(A, len);
  return 0;
}

ヒープソート実装(再帰的でない汎用版)
汎用性を満たすために,本論文では同様にライブラリ関数qsortソートアルゴリズムに類似した汎用版を実現した.

#include <stdio.h>

#define LEFT(i) (((i) << 1) + 1)
#define RIGHT(i) (((i) << 1) + 2)
#define PARENT(i) (((i) - 1) >> 1)

#define SWAP(a, b, size) \
  do {                                        \
  size_t __size = (size);                     \
  unsigned char *__a = (a), *__b = (b);       \
  do {                                        \
    unsigned char __tmp = *__a;               \
    *__a++ = *__b;                            \
    *__b++ = __tmp;                           \
  } while (--__size > 0);                     \
  } while(0)

void display(int *A, int len)
{
  int i;

  for (i = 0; i < len; i++) {
    printf("%d ", A[i]);
  }
  printf("
");
}

/* @brief The hsort() function sorts an array with nmemb * elements of size size. * @param base [in] The start of the array. * @param nmemb [in] The number of elements in array. * @param size [in] The size of the element. * @param compare [in] The comparison function. */
void hsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *))
{
  int l, r, i, largest;

  i = PARENT(nmemb - 1);  /* Get the last non-leaf node */

  /* First build heap */
  while (i >= 0) {
    l = LEFT(i);
    r = RIGHT(i);

    largest = i;
    if (l < nmemb && compare(base + l * size, base + largest * size) > 0) {
      largest = l;
    }

    if (r < nmemb && compare(base + r * size, base + largest * size) > 0) {
      largest = r;
    }

    if (largest == i) {
      i--;
    } else {
      SWAP(base + i * size, base + largest * size, size);
      i = largest;
    }
  }

  while (--nmemb > 0) {
    SWAP(base, base + nmemb * size, size);  /* Sort: get the max element */

    i = 0;              /* Heapify */
    while (1) {
      l = LEFT(i);
      r = RIGHT(i);

      largest = i;
      if (l < nmemb && compare(base + l * size, base + largest * size) > 0) {
        largest = l;
      }

      if (r < nmemb && compare(base + r * size, base + largest * size) > 0) {
        largest = r;
      }

      if (largest == i) {
        break;
      }

      SWAP(base + i * size, base + largest * size, size);
      i = largest;
    }
  }
}

int compare(const void *a, const void *b)
{
  return *(int *)a - *(int *)b;
}

int main()
{
  int A[] = {10, 32, 43, 31, 2, 45, 12, 9, 71, 41, 10, -19, 32, 4, 8, 6};
  int len = sizeof(A) / sizeof(A[0]);

  display(A, len);

  hsort(A, len, sizeof(int), compare);

  display(A, len);
  return 0;
}