fork download 
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <tchar.h>
  5. #include <conio.h>
  6. #include <string.h>
  7.  
  8. #include <Windows.h>
  9. #include <vector>
  10. #include <algorithm>
  11.  
  12.  
  13. #define N 10000000
  14.  
  15. int compare(const void *p, const void *q)
  16. {
  17. 	register double p0 = *(double*)p;
  18. 	register double q0 = *(double*)q;
  19. 	if (p0 > q0) return 1;
  20. 	if (p0 < q0) return -1;
  21. 	return 0;
  22. }
  23. #define MAXSTACK 2048
  24. void qSortI(double *a, long size) {
  25. 	long i, j;
  26. 	long lb, ub;
  27. 	long lbstack[MAXSTACK], ubstack[MAXSTACK];
  28.  
  29. 	long stackpos = 1;
  30. 	long ppos;
  31. 	double pivot;
  32. 	double temp; 
  33.  
  34. 	lbstack[1] = 0;
  35. 	ubstack[1] = size-1;
  36.  
  37. 	do {
  38. 		lb = lbstack[ stackpos ];
  39. 		ub = ubstack[ stackpos ];
  40. 		stackpos--;
  41. 		do {
  42. 			ppos = ( lb + ub ) >> 1;
  43. 			i = lb; j = ub; pivot = a[ppos];
  44.  
  45. 			do {
  46. 				while ( a[i] < pivot ) i++;
  47. 				while ( pivot < a[j] ) j--;
  48.  
  49. 				if ( i <= j ) {
  50. 					temp = a[i]; a[i] = a[j]; a[j] = temp;
  51. 					i++; j--;
  52. 				}
  53. 			} while ( i <= j );
  54. 			if ( i < ppos ) {
  55. 				if ( i < ub ) {
  56. 					stackpos++;
  57. 					lbstack[ stackpos ] = i;
  58. 					ubstack[ stackpos ] = ub;
  59. 				}
  60. 				ub = j;
  61. 			} else {
  62. 				if ( j > lb ) { 
  63. 					stackpos++;
  64. 					lbstack[ stackpos ] = lb;
  65. 					ubstack[ stackpos ] = j;
  66. 				}
  67. 				lb = i;
  68. 			}
  69. 		} while ( lb < ub );
  70. 	} while ( stackpos != 0 );
  71. }
  72.  
  73. void test_c()
  74. {
  75. 	double *buf = (double*)malloc(sizeof(double) * N);
  76. 	int i = 0;
  77.  
  78. 	for (i = 0; i < N; i++)
  79. 		buf[i] = rand() + ( (double)rand() / 100000);
  80.  
  81. 	qsort(buf, N, sizeof(double), compare);
  82.  
  83. 	free(buf);
  84. }
  85.  
  86. void test_c2()
  87. {
  88. 	double *buf = (double*)malloc(sizeof(double) * N);
  89. 	int i = 0;
  90.  
  91. 	for (i = 0; i < N; i++)
  92. 		buf[i] = rand() + ( (double)rand() / 100000);
  93.  
  94. 	qSortI(buf, N);
  95. 	//printf("%f %f %f %f\n", buf[0], buf[10], buf[N-11], buf[N-1]);
  96.  
  97. 	free(buf);
  98. }
  99.  
  100. void test_cplusplus()
  101. {
  102. 	std::vector<double> buf;
  103. 	for (int i = 0; i < N; i++)
  104. 		buf.push_back( rand() + ( (double)rand() / 100000) );
  105.  
  106. 	std::sort(buf.begin(), buf.end() );
  107. }
  108.  
  109. typedef void (*test_proc)();
  110.  
  111. double test(test_proc proc)
  112. {
  113. 	LARGE_INTEGER start, stop, freq;
  114. 	srand(GetTickCount());
  115. 	QueryPerformanceCounter(&start);
  116.  
  117. 	proc();
  118.  
  119. 	QueryPerformanceCounter(&stop);
  120. 	QueryPerformanceFrequency(&freq);
  121. 	return double(stop.LowPart - start.LowPart) / freq.LowPart;
  122. }
  123.  
  124. int _tmain(int argc, _TCHAR* argv[])
  125. {
  126. 	printf("test_c Result: %f\n", test(test_c) );
  127. 	printf("test_cplusplus Result: %f\n", test(test_cplusplus) );
  128. 	printf("test_c2 Result: %f\n", test(test_c2) );
  129.  
  130. 	getchar();
  131. 	return 0;
  132. }
  133.  
  134.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/iL6Gb
language:
C++ (gcc 8.3)
created:
13 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!