fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>	/* 疑似乱数生成時に必要 */
  3. #include <time.h>	/* 実行毎に異なる疑似乱数を発生させる為必要 */
  4.  
  5. /* マクロ定義 */
  6. #define NUM_DATA 10	/* 要素数 */
  7.  
  8. /* グローバル変数 */
  9. int a[NUM_DATA] = { 54, 41, 18, 31, 70, 17, 60, 89, 36, 98, };
  10.  
  11. /* プロトタイプ宣言 */
  12. void SetData();			/* データを作成 */
  13. void ShowData();		/* ヒープを構成する */
  14. void HeapMain(int n);		/* ヒープソートを行う */
  15. void InitializeHeap(int n);	/* ヒープを構成する */
  16. void DownHeap(int k, int r);	/* ヒープを正しく作り直す(ダウンヒープを行う) */
  17. /*
  18. int main()
  19. {
  20. int i;
  21. int n = NUM_DATA;
  22.  
  23. srand((unsigned)time(NULL));
  24.  
  25. SetData();
  26.  
  27. puts("ソート前");
  28. ShowData();
  29. printf("\n");
  30.  
  31. puts("ヒープ構成過程を表示");
  32. InitializeHeap(n);
  33. printf("\n");
  34.  
  35. HeapMain(n);
  36. puts("ヒープソート実行後");
  37. ShowData();
  38.  
  39. return 0;
  40. }
  41. */
  42. void SetData_Fix(int a[], int N)
  43. {
  44. 	int i;		/* ループカウンタ */
  45. 	double rd;	/* [0,1)の実数乱数を格納する */
  46.  
  47. 	for (i = 0; i < N; i++) {
  48. 		rd = rand() / (RAND_MAX + 1.0);	/* [0,1)の実数乱数を生成 */
  49. 		a[i] = (int)(100 + 1) * rd;	/* 0以上100以下の整数乱数を生成 */
  50. 	}
  51. }
  52. void ShowData_Fix(int a[], int N)
  53. {
  54. 	int i;
  55.  
  56. 	for (i = 0; i < N; i++) {
  57. 		printf("%d, ", a[i]);
  58. 	}
  59. 	printf("\n");
  60. }
  61. void DownHeap_Fix(int a[],int k, int r)
  62. {
  63. 	int j;		/* ループカウンタ */
  64. 	int tmp;	/* 一時格納変数 */
  65.  
  66. 	j = 2 * k + 1;	/* 最初は(とりあえず)左の子の添え字番号をjに代入 */
  67. 	while (j <= r) {
  68. 		if ((j != r) && (a[j + 1] > a[j]))	/* j != r 左右両方の子供が存在するとき */
  69. 			/* j には左右の子のうち大きい方の添え字番号を代入 */
  70. 			j = j + 1;			/* a[j] とa[j + 1] を比較して大きい方をj とする */
  71. 		if (a[k] >= a[j]) {	/* a[k] がa[j] 以上ならば終了 */
  72. 			break;			/* whileループを抜ける */
  73. 		}
  74. 		else {	/* そうでなければ，a[k]とa[j]の値を入れ替え */
  75. 			tmp = a[k];
  76. 			a[k] = a[j];
  77. 			a[j] = tmp;
  78.  
  79. 			/* kとjの値を入れ替える */
  80. 			tmp = k;
  81. 			k = j;
  82. 			j = 2 * tmp + 1;	/* 左の子の添え字番号をjに代入 */
  83. 		}
  84. 	}
  85. }
  86. void InitializeHeap_Fix(int a[],int n)
  87. {
  88. 	int i;	/* ループカウンタ */
  89. 	int k;	/* ダウンヒープを開始する頂点番号 */
  90. 	int r;	/* ヒープの要素数 */
  91.  
  92. 	/* i = n / 2 - 1 初期値は親ノードの添え字を設定 */
  93. 	for (i = n / 2 - 1; i >= 0; i--) {
  94. 		k = i; 		/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  95. 		r = n - 1;	/* 現在のヒープの要素数- 1 */
  96. 		DownHeap_Fix(a,k, r);	/* ダウンヒープ */
  97. 		ShowData_Fix(a,n);		/* ダウンヒープの実行過程を表示 */
  98. 	}
  99. }
  100. void HeapMain_Fix(int a[], int n)
  101. {
  102. 	int i;			/* ループカウンタ */
  103. 	int k;			/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  104. 	int r;			/* ヒープの要素数 */
  105. 	int tmp;		/* 一時格納変数 */
  106.  
  107. 	if (n <= 0) return;
  108.  
  109. 	i = n - 1;		/* 末尾の要素の前の要素 */
  110. 	while (i >= 0) {
  111. 		tmp = a[0]; 	/* 根の値(※最大値になってるはず)と最後の頂点(末尾の要素)を入れ替える */
  112. 		a[0] = a[i];
  113. 		a[i] = tmp;
  114. 		i--;			/* 最後の頂点(末尾の要素)をヒープから除外する */
  115. 		k = 0; 			/* ダウンヒープを開始する頂点番号 */
  116. 		r = i;			/* 最後の頂点(末尾の要素)を除外した後のヒープ要素数 */
  117. 		DownHeap_Fix(a, k, r);	/* ダウンヒープ */
  118. 	}
  119. 	a += 2;
  120. 	n -= 2;
  121. 	InitializeHeap_Fix(a, n);
  122. 	HeapMain_Fix(a, n);
  123.  
  124. }
  125.  
  126. void StartA(int Data[], int N){
  127. 	InitializeHeap_Fix(Data, N);
  128. 	HeapMain_Fix(Data, N);
  129. 	puts("AfterA:");
  130. 	ShowData_Fix(Data, N);
  131. }
  132.  
  133. void StartB(int N){
  134. 	InitializeHeap(N);
  135. 	HeapMain(N);
  136. 	puts("AfterB:");
  137. 	ShowData();
  138. }
  139. int main(){
  140.  
  141. 	int Data[NUM_DATA] = { 54, 41, 18, 31, 70, 17, 60, 89, 36, 98, };
  142.  
  143. 	puts("BeforeA:");
  144. 	ShowData_Fix(Data,NUM_DATA);
  145. 	puts("");
  146. 	StartA(Data, NUM_DATA);
  147.  
  148. 	puts("\n");
  149.  
  150. 	puts("BeforeB:");
  151. 	ShowData();
  152. 	puts("");
  153. 	StartB(NUM_DATA);
  154.  
  155. 	return 0;
  156. }
  157. /* データを作成 */
  158. void SetData()
  159. {
  160. 	int i;		/* ループカウンタ */
  161. 	double rd;	/* [0,1)の実数乱数を格納する */
  162.  
  163. 	for (i = 0; i < NUM_DATA; i++) {
  164. 		rd = rand() / (RAND_MAX + 1.0);	/* [0,1)の実数乱数を生成 */
  165. 		a[i] = (int)(100 + 1) * rd;	/* 0以上100以下の整数乱数を生成 */
  166. 	}
  167. }
  168.  
  169. /* 各要素を表示 */
  170. void ShowData()
  171. {
  172. 	int i;
  173.  
  174. 	for (i = 0; i < NUM_DATA; i++) {
  175. 		printf("%d, ", a[i]);
  176. 	}
  177. 	printf("\n");
  178. }
  179.  
  180. /* ヒープソートを行う */
  181. /* ヒープから最大値を取り出して，ヒープの大きさを1減らして，
  182. DownHeapを用いてヒープを再構築する，という操作を繰り返す */
  183. void HeapMain(int n)
  184. {
  185. 	int i;			/* ループカウンタ */
  186. 	int k;			/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  187. 	int r;			/* ヒープの要素数 */
  188. 	int tmp;		/* 一時格納変数 */
  189.  
  190. 	i = n - 1;		/* 末尾の要素の前の要素 */
  191. 	while (i >= 0) {
  192. 		tmp = a[0]; 	/* 根の値(※最大値になってるはず)と最後の頂点(末尾の要素)を入れ替える */
  193. 		a[0] = a[i];
  194. 		a[i] = tmp;
  195. 		i--;			/* 最後の頂点(末尾の要素)をヒープから除外する */
  196. 		k = 0; 			/* ダウンヒープを開始する頂点番号 */
  197. 		r = i;			/* 最後の頂点(末尾の要素)を除外した後のヒープ要素数 */
  198. 		DownHeap(k, r);	/* ダウンヒープ */
  199. 	}
  200. }
  201.  
  202. /* ヒープを構成する */
  203. /* 木を2つずつ組み合わせる操作を続けて，全体として1つの木にを作る(ヒープが完成) */
  204. void InitializeHeap(int n)
  205. {
  206. 	int i;	/* ループカウンタ */
  207. 	int k;	/* ダウンヒープを開始する頂点番号 */
  208. 	int r;	/* ヒープの要素数 */
  209.  
  210. 	/* i = n / 2 - 1 初期値は親ノードの添え字を設定 */
  211. 	for (i = n / 2 - 1; i >= 0; i--) {
  212. 		k = i; 		/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
  213. 		r = n - 1;	/* 現在のヒープの要素数- 1 */
  214. 		DownHeap(k, r);	/* ダウンヒープ */
  215. 		ShowData();		/* ダウンヒープの実行過程を表示 */
  216. 	}
  217. }
  218.  
  219. /* ヒープを正しく作り直す */
  220. void DownHeap(int k, int r)
  221. {
  222. 	int j;		/* ループカウンタ */
  223. 	int tmp;	/* 一時格納変数 */
  224.  
  225. 	j = 2 * k + 1;	/* 最初は(とりあえず)左の子の添え字番号をjに代入 */
  226. 	while (j <= r) {
  227. 		if ((j != r) && (a[j + 1] > a[j]))	/* j != r 左右両方の子供が存在するとき */
  228. 			/* j には左右の子のうち大きい方の添え字番号を代入 */
  229. 			j = j + 1;			/* a[j] とa[j + 1] を比較して大きい方をj とする */
  230. 		if (a[k] >= a[j]) {	/* a[k] がa[j] 以上ならば終了 */
  231. 			break;			/* whileループを抜ける */
  232. 		}
  233. 		else {	/* そうでなければ，a[k]とa[j]の値を入れ替え */
  234. 			tmp = a[k];
  235. 			a[k] = a[j];
  236. 			a[j] = tmp;
  237.  
  238. 			/* kとjの値を入れ替える */
  239. 			tmp = k;
  240. 			k = j;
  241. 			j = 2 * tmp + 1;	/* 左の子の添え字番号をjに代入 */
  242. 		}
  243. 	}
  244. }
  245.  
Success #stdin #stdout 0s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
BeforeA:
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, 
70, 54, 31, 98, 41, 60, 89, 36, 
70, 54, 89, 98, 41, 31, 60, 36, 
70, 98, 89, 54, 41, 31, 60, 36, 
98, 89, 70, 54, 41, 31, 60, 36, 
41, 54, 98, 70, 89, 60, 
41, 89, 98, 54, 70, 60, 
98, 60, 89, 54, 41, 70, 
60, 98, 89, 70, 
98, 89, 70, 60, 
98, 89, 
AfterA:
17, 18, 31, 36, 41, 54, 60, 70, 89, 98, 


BeforeB:
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, 
AfterB:
17, 18, 70, 54, 31, 36, 41, 60, 89, 98,
https://ideone.com/rXCceP
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!