fork download
copy 
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <sys/time.h>
  4. #include <stdlib.h>
  5.  
  6. #define size 1000
  7.  
  8. void heap(void);
  9. void heapSort(void);
  10. void swap(int *, int *);
  11. void viewTree(void);
  12. void heapDown(int);
  13.  
  14. long getTime(void);
  15.  
  16. int array[size];
  17.  
  18. int m = size - 1;
  19.  
  20. main(){
  21.  
  22. 	for(int x = 0; x < size; x++){
  23. 		array[x] = rand() % 100000;
  24. 	}
  25.  
  26. 	//viewTree();
  27.  
  28. 	heap();
  29. 	//viewTree();
  30.  
  31. 	//printf("\n");
  32.  
  33. 	heapSort();
  34. 	//viewTree();
  35.  
  36. 	long t = getTime();
  37.  
  38. 	printf("%ld\n", t);
  39.  
  40. }
  41.  
  42. void heap(){
  43. 	//ヒープ
  44.  
  45. 	int i;
  46.  
  47. 	for(i = (m-1) / 2; i >= 0; i--){
  48. 		heapDown(i);
  49. 	}
  50.  
  51. }
  52.  
  53. void heapSort(){
  54. 	//切り離し
  55.  
  56. 	while(m >= 1){
  57.  
  58. 		heap();
  59. 		swap(&array[0], &array[m]);
  60. 		//viewTree();
  61. 		m--;
  62.  
  63. 	}
  64.  
  65. }
  66.  
  67. void swap(int *x, int *y){
  68. 	//入れ替え
  69.  
  70. 	int tmp;
  71.  
  72. 	tmp = *x;
  73. 	*x = *y;
  74. 	*y = tmp;
  75.  
  76. }
  77.  
  78. void viewTree(){
  79. 	//木の表示
  80.  
  81. 	int i, j;
  82.  
  83. 	for(i = 1; i <= size; i *= 2){
  84.  
  85. 		for(j = 0; j < i; j++){
  86. 			printf("%d", array[i+j-1]);
  87. 		}
  88.  
  89. 		printf("\n");
  90.  
  91. 	}
  92.  
  93. }
  94.  
  95. void heapDown(int j){
  96. 	//ヒープ
  97.  
  98. 	if(2 * j + 2 <= m && array[j] < array[2*j+2] && array[2*j+1] < array[2*j+2]){
  99. 		swap(&array[j], &array[2*j+2]);
  100. 		heapDown(2*j+2);
  101. 	}
  102. 	else if(2 * j + 1 <= m && array[j] < array[2*j+1]){
  103. 		swap(&array[j], &array[2*j+1]);
  104. 		heapDown(2*j+1);
  105. 	}
  106.  
  107. }
  108.  
  109. long getTime(){
  110.  
  111. 	struct timeval t;
  112.  
  113. 	gettimeofday(&t, NULL);
  114.  
  115. 	localtime(&t.tv_sec);
  116.  
  117. 	return time(NULL) * 1000 + t.tv_usec / 1000;
  118.  
  119. }
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1669892052905
https://ideone.com/Dwt8Lb
language:
C (gcc 8.3)
created:
1 year 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!