Heap Sort implemented in C

heapsort.c

/* Copyright(C) 2012 Kazh. All Rights Reserved. */

#include <stddef.h>
#include "heapsort.h"

/** 引数の不正を検査する */
#ifdef DEBUG
#  include <stdio.h>
#  include <stdlib.h>
#  define VALIDATE(E) \
   { \
     if ( !(E) ) \
     { \
       fputs ( "Fatal Error Reported:\n", stderr ); \
       fputs ( "  Validation ``" #E "\" failed!!\n\n", stderr ); \
       exit ( 5 ); \
     } \
   }
#else /* DEBUG */
#  define VALIDATE(E) \
   { \
     if ( !(E) ) return ; \
   }
#endif /* DEBUG */

/** インデックスをアドレスに変換する */
#define ADDRESS(INDEX,BASE,WIDTH) \
  ( (BASE) + (INDEX) * (WIDTH) )

/** 親ノードのインデックスを取得する */
#define PARENT(INDEX) \
  ( ( (INDEX) - 1 ) / 2 )
/** 第1 子ノードのインデックスを取得する */
#define CHILD1(INDEX) \
  ( (INDEX) * 2 + 1 )
/** 第2 子ノードのインデックスを取得する */
#define CHILD2(INDEX) \
  ( (INDEX) * 2 + 2 )

/** 親ノードのアドレスを取得する */
#define PARENT_ADDRESS(INDEX,BASE,WIDTH) \
  ADDRESS( PARENT(INDEX), BASE, WIDTH )
/** 第1 子ノードのアドレスを取得する */
#define CHILD1_ADDRESS(INDEX,BASE,WIDTH) \
  ADDRESS( CHILD1(INDEX), BASE, WIDTH )
/** 第2 子ノードのアドレスを取得する */
#define CHILD2_ADDRESS(INDEX,BASE,WIDTH) \
  ADDRESS( CHILD2(INDEX), BASE, WIDTH )

/** 2 値を交換する */
static void
swap (
  /** 1 つ目の交換対象 */
  void   *a,
  /** 2 つ目の交換対象 */
  void   *b,
  /** 交換対象のデータ長 */
  size_t  len
  )
{
  char *const a_ptr = (char *)a;
  char *const b_ptr = (char *)b;
  size_t i;

  for ( i = 0; i < len; ++i )
  {
    const char t = a_ptr[ i ];
    a_ptr[ i ] = b_ptr[ i ];
    b_ptr[ i ] = t;
  }

  return ;
}

void
heapsort (
  void   *base,
  size_t  num,
  size_t  width,
  int   (*compare)( const void *, const void * )
  )
{
  char *const base_ptr = (char *)base;
  size_t i, j;

  VALIDATE( base != NULL );
  VALIDATE( width > 0 );

  /* ヒープの構築 */
  for ( i = 1; i < num; ++i )
  {
    for ( j = i; j != 0; j = PARENT( j ) )
    {
      char *const current_adrs = ADDRESS( j, base_ptr, width );
      char *const parent_adrs = PARENT_ADDRESS( j, base_ptr, width );

      if ( compare ( current_adrs, parent_adrs ) > 0 )
      {
        swap ( current_adrs, parent_adrs, width );
      }
      else break ;
    }
  }

  /* ヒープから整列 */
  for ( i = num - 1; i > 0; --i )
  {
    swap ( ADDRESS( 0, base_ptr, width )
         , ADDRESS( i, base_ptr, width ), width );

    /* ヒープの再構築 */
    for ( j = 0; ; )
    {
      char *const current_adrs = ADDRESS( j, base_ptr, width );
      char *child_adrs;
      int child_slct;

      /* 最大値をとる子を選択 */
      if ( CHILD2( j ) < i )
      {
        if ( compare ( CHILD1_ADDRESS( j, base_ptr, width )
                     , CHILD2_ADDRESS( j, base_ptr, width ) ) > 0 )
        {
          child_slct = CHILD1( j );
        }
        else
        {
          child_slct = CHILD2( j );
        }
      }
      else if ( CHILD1( j ) < i )
      {
        child_slct = CHILD1( j );
      }
      else break ;

      child_adrs = ADDRESS( child_slct, base_ptr, width );
      if ( compare ( child_adrs, current_adrs ) > 0 )
      {
        swap ( child_adrs, current_adrs, width );
        j = child_slct;
      }
      else break ;
    }
  }

  return ;
}

#ifdef UTEST
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N ( 1 << 24 )
#define INT(X) \
  ( *( (const int *)(X) ) )

int d[ N ];

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

/** 単体テスト実行ルーチン(UTEST が有効だと実行する) */
int
main (
  int   argc,
  char *argv[ ]
  )
{
  int i, j;

  srand ( (unsigned int)time ( NULL ) );

  for ( i = 1; i <= N; i = i * 2 )
  {
    clock_t tob, toe;

    for ( j = 0; j < i; ++j )
    {
      d[ j ] = rand ( ) % 100;
    }
    printf ( "TEST( N = %d ) => ", i ); fflush ( stdout );

    tob = clock ( );
    heapsort ( d, i, sizeof ( int ), compare );
    toe = clock ( );

    for ( j = 1; j < i; ++j )
    {
      if ( d[ j - 1 ] > d[ j ] ) break ;
    }
    printf ( "%s [%.3fsec]\n"
           , j == i ? "ok" : "ng"
           , (double)( toe - tob ) / CLOCKS_PER_SEC );
    if ( j != i ) break ;
  }

  return ( 0 );
}
#endif /* UTEST */

heapsort.h

/***********************************************************
 * Kazh's Library 2 - Heap Sort
 *   Copyright(C) 2012 Kazh. All Rights Reserved.
***********************************************************/

#ifndef INC_HEAPSORTH
#define INC_HEAPSORTH

#include <stddef.h>

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

/** ヒープソートによって与えられた配列をソートする */
extern void
heapsort (
  /** [in,out] ソート対象配列の先頭アドレス */
  void  * base,
  /** [in] 配列の要素数 */
  size_t  num,
  /** [in] 1 要素当たりのサイズ */
  size_t  width,
  /** [in] 比較関数 */
  int  (* compare)( const void *, const void * )
  );

#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /* INC_HEAPSORTH */

output.txt

TEST( N = 1 ) => ok [0.000sec]
TEST( N = 2 ) => ok [0.000sec]
TEST( N = 4 ) => ok [0.000sec]
TEST( N = 8 ) => ok [0.000sec]
TEST( N = 16 ) => ok [0.000sec]
TEST( N = 32 ) => ok [0.000sec]
TEST( N = 64 ) => ok [0.000sec]
TEST( N = 128 ) => ok [0.000sec]
TEST( N = 256 ) => ok [0.000sec]
TEST( N = 512 ) => ok [0.000sec]
TEST( N = 1024 ) => ok [0.000sec]
TEST( N = 2048 ) => ok [0.000sec]
TEST( N = 4096 ) => ok [0.000sec]
TEST( N = 8192 ) => ok [0.000sec]
TEST( N = 16384 ) => ok [0.000sec]
TEST( N = 32768 ) => ok [0.010sec]
TEST( N = 65536 ) => ok [0.010sec]
TEST( N = 131072 ) => ok [0.020sec]
TEST( N = 262144 ) => ok [0.040sec]
TEST( N = 524288 ) => ok [0.080sec]
TEST( N = 1048576 ) => ok [0.160sec]
TEST( N = 2097152 ) => ok [0.360sec]
TEST( N = 4194304 ) => ok [0.790sec]
TEST( N = 8388608 ) => ok [1.680sec]
TEST( N = 16777216 ) => ok [3.480sec]