fork(1) download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>	/* 疑似乱数生成時に必要 */
  4. #include <time.h>	/* 実行毎に異なる疑似乱数を発生させる為必要 */
  5.  
  6. /* マクロ定義 */
  7. #define NUM_DATA 10	/* 要素数 */
  8.  
  9. /* グローバル変数 */
  10. int a[ NUM_DATA ];
  11.  
  12. /* プロトタイプ宣言 */
  13. void SetData();			/* データを作成 */
  14. void ShowData();		/* ヒープを構成する */
  15. void HeapMain( int n );		/* ヒープソートを行う */
  16. void InitializeHeap( int n );	/* ヒープを構成する */
  17. void DownHeap( int k, int r );	/* ヒープを正しく作り直す(ダウンヒープを行う) */
  18.  
  19. int main( )
  20. {
  21. 	int i;			/* ループカウンタ */
  22. 	int n = NUM_DATA;	/* 要素数 */
  23.  
  24. 	srand( (unsigned) time( NULL ) );	/* 実行毎に異なる疑似乱数を発生させる */
  25.  
  26. 	SetData( );		/* データを作成 */
  27.  
  28. 	puts( "ソ\ート前" );
  29. 	ShowData( );		/* 部分順序木構成前のデータを表示 */
  30. 	printf( "\n" );
  31.  
  32. 	puts( "ヒープ構\成過程を表\示" );
  33. 	InitializeHeap( n );	/* ヒープを構成する */
  34. 	printf( "\n" );
  35.  
  36. 	HeapMain( n );		/* ヒープソートを行う */
  37. 	puts( "ヒープソ\ート実行後" );
  38. 	ShowData( );		/* ソート後のデータを表示 */
  39.  
  40. 	return 0;
  41. }
  42.  
  43. /* データを作成 */
  44. void SetData( )
  45. {
  46. 	int i;		/* ループカウンタ */
  47. 	double rd;	/* [0,1)の実数乱数を格納する */
  48.  
  49. 	for( i = 0; i < NUM_DATA; i++ ) {
  50. 		rd = rand() / ( RAND_MAX + 1.0 );	/* [0,1)の実数乱数を生成 */
  51. 		a[ i ] = (int) ( 100 + 1 ) * rd;	/* 0以上100以下の整数乱数を生成 */
  52. 	}
  53. }
  54.  
  55. /* 各要素を表示 */
  56. void ShowData( )
  57. {
  58. 	int i;
  59.  
  60. 	for( i = 0; i < NUM_DATA; i++) {
  61. 		printf( "%d, ", a[ i ]);
  62. 	}
  63. 	printf( "\n" );
  64. }
  65.  
  66. /* ヒープソートを行う */
  67. /* ヒープから最大値を取り出して，ヒープの大きさを1減らして，
  68. DownHeapを用いてヒープを再構築する，という操作を繰り返す */
  69. void HeapMain( int n )
  70. { 
  71. 	int i;			/* ループカウンタ */
  72. 	int k;			/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  73. 	int r;			/* ヒープの要素数 */
  74. 	int tmp;		/* 一時格納変数 */
  75.  
  76. 	i = n - 1;		/* 末尾の要素の前の要素 */
  77. 	while( i >= 0 ) {
  78. 		tmp = a[0]; 	/* 根の値(※最大値になってるはず)と最後の頂点(末尾の要素)を入れ替える */
  79. 		a[0] = a[i]; 	
  80. 		a[i] = tmp;
  81. 		i--;			/* 最後の頂点(末尾の要素)をヒープから除外する */
  82. 		k = 0; 			/* ダウンヒープを開始する頂点番号 */
  83. 		r = i;			/* 最後の頂点(末尾の要素)を除外した後のヒープ要素数 */
  84. 		DownHeap( k, r );	/* ダウンヒープ */
  85. 	}
  86. }
  87.  
  88. /* ヒープを構成する */
  89. /* 木を2つずつ組み合わせる操作を続けて，全体として1つの木にを作る(ヒープが完成) */
  90. void InitializeHeap( int n )
  91. { 
  92. 	int i;	/* ループカウンタ */
  93. 	int k;	/* ダウンヒープを開始する頂点番号 */
  94. 	int r;	/* ヒープの要素数 */
  95.  
  96. 	/* i = n / 2 - 1 初期値は親ノードの添え字を設定 */
  97. 	for( i = n / 2 - 1; i >= 0; i-- ) {
  98. 		k = i; 		/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  99. 		r = n - 1;	/* 現在のヒープの要素数- 1 */
  100. 		DownHeap( k, r );	/* ダウンヒープ */
  101. 		ShowData( );		/* ダウンヒープの実行過程を表示 */
  102. 	} 
  103. }
  104.  
  105. /* ヒープを正しく作り直す */
  106. void DownHeap( int k, int r )
  107. { 
  108. 	int j;		/* ループカウンタ */
  109. 	int tmp;	/* 一時格納変数 */
  110.  
  111. 	j = 2 * k + 1;	/* 最初は(とりあえず)左の子の添え字番号をjに代入 */
  112. 	while( j <= r ) {
  113. 		if( (j != r) && ( a[j+1] > a[j] ) )	/* j != r 左右両方の子供が存在するとき */
  114. 			/* j には左右の子のうち大きい方の添え字番号を代入 */
  115. 			j = j + 1;			/* a[j] とa[j + 1] を比較して大きい方をj とする */
  116. 			if( a[ k ] >= a[ j ] ) {	/* a[k] がa[j] 以上ならば終了 */
  117. 				break;			/* whileループを抜ける */
  118. 			}
  119. 			else {	/* そうでなければ，a[k]とa[j]の値を入れ替え */
  120. 				tmp = a[ k ]; 
  121. 				a[ k ] = a[ j ]; 
  122. 				a[ j ] = tmp;
  123.  
  124. 				/* kとjの値を入れ替える */
  125. 				tmp = k; 		
  126. 				k = j; 			
  127. 				j = 2 * tmp + 1;	/* 左の子の添え字番号をjに代入 */
  128. 			}
  129. 	}
  130. }
Success #stdin #stdout 0s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ソート前
54, 41, 18, 31, 70, 17, 60, 89, 36, 98, 

ヒープ構成過程を表示
54, 41, 18, 31, 98, 17, 60, 89, 36, 70, 
54, 41, 18, 89, 98, 17, 60, 36, 31, 70, 
54, 41, 60, 89, 98, 17, 18, 36, 31, 70, 
54, 98, 60, 70, 89, 17, 18, 36, 31, 41, 
98, 60, 89, 70, 54, 17, 18, 36, 31, 41, 

ヒープソート実行後
17, 18, 70, 54, 31, 36, 41, 60, 89, 98,
https://ideone.com/HOlaTT
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!