fork download
copy 
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <sys/time.h>
  4. #define len 10000
  5. int a[len];
  6. int b[len];
  7. int m=len-1;
  8.  
  9. void makec(){
  10. 	for(int i=0;i<len;i++){
  11. 		int r=rand()%len;
  12. 		a[i]=r;
  13. 		b[i]=r;
  14. 	}
  15. }
  16.  
  17. void swap(int* a,int* b){
  18. 	int tmp;
  19. 	tmp=*a;
  20. 	*a=*b;
  21. 	*b=tmp;
  22. }
  23.  
  24. void quickSort(left,right){
  25. 	if(left>=right){
  26. 		return;
  27. 	}
  28. 	int i=left+1;
  29. 	int j=right;
  30. 	while(1){
  31. 		while(a[i]<=a[left]&&i<right){
  32. 		    i++;
  33. 	    }
  34. 	    while(a[j]>=a[left]&&j>left){
  35. 		    j--;
  36. 	    }
  37. 	    if(i>=j){
  38. 		    break;
  39. 	    }
  40. 	    swap(&a[i],&a[j]);
  41. 	}
  42. 	swap(&a[left],&a[j]);
  43. 	quickSort(left,j-1);
  44. 	quickSort(j+1,right);
  45. }
  46.  
  47. void heap(){
  48. 	int i,j;
  49. 	for(i=(m-1)/2;i>=0;i--){
  50. 		j=i;
  51. 		heapDown(j);
  52. 	}
  53. }
  54.  
  55. void heapDown(int j){
  56. 	if(2*j+2<=m&&b[j]<b[2*j+2]&&b[2*j+1]<b[2*j+2]){
  57. 		swap(&b[j],&b[2*j+2]);
  58. 		return heapDown(2*j+2);
  59. 	}
  60. 	else if(2*j+1<=m&&b[j]<b[2*j+1]){
  61. 		swap(&b[j],&b[2*j+1]);
  62. 		return heapDown(2*j+1);	
  63. 	}
  64.  
  65. }
  66.  
  67. void heapSort(){
  68. 	while(m>=1){
  69. 		heap();
  70. 		swap(&b[0],&b[m]);
  71. 		m--;
  72. 	}
  73. }
  74.  
  75. long getTime() { 
  76.     struct timeval t; 
  77.     gettimeofday(&t, NULL); 
  78.     localtime(&t.tv_sec); 
  79.     return time(NULL)*1000 + t.tv_usec/1000;
  80. }
  81.  
  82. main(){
  83. 	makec();
  84. 	long start1=getTime();
  85. 	quickSort(0,len-1);
  86. 	long end1=getTime();
  87. 	long start2=getTime();
  88. 	heapSort();
  89. 	long end2=getTime();
  90. 	printf("クイックソート：%06d\n",end1-start1);
  91. 	printf("ヒープソート：%06d\n",end2-start2);
  92. }
  93.  
Success #stdin #stdout 0.11s 5416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
クイックソート：000001
ヒープソート：000102
https://ideone.com/IvUyhh
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!