fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>
  4. #include <stdint.h>
  5. #include <sys/time.h>
  6.  
  7. #define ELEMS 10000000
  8. #define TOPSS 300000
  9.  
  10. typedef double val_t;
  11.  
  12. inline static double baka_sec_count(void) {
  13.     struct timeval tv;
  14.     gettimeofday(&tv, NULL);
  15. 	return (double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0);
  16. }
  17.  
  18. inline static uint32_t rand32() {
  19. 	static uint32_t y = 2463534242;
  20. 	y = y ^ (y << 13);
  21. 	y = y ^ (y >> 17);
  22. 	return y = y ^ (y << 15);
  23. }
  24.  
  25. inline static uint64_t rand64(void) {
  26. 	static uint64_t x = 88172645463325252ULL;
  27. 	x = x ^ (x << 13);
  28. 	x = x ^ (x >> 7);
  29. 	return x = x ^ (x << 17);
  30. }
  31.  
  32. inline static val_t* alloc_data(int n_) {
  33. 	val_t* p = (val_t*)malloc(sizeof(val_t) * n_);
  34.  
  35. 	for (int i = 0; i < n_; ++i) {
  36. 		p[i] = rand64();
  37. 	}
  38.  
  39. 	return p;
  40. }
  41.  
  42. inline static val_t* alloc_saiaku_data(int n_) {
  43. 	val_t* p = (val_t*)malloc(sizeof(val_t) * n_);
  44.  
  45. 	for (int i = 0; i < n_ / 2 ; ++i) {
  46. 		p[i] = i;
  47. 	}
  48. 	for (int i = n_ / 2; i < n_; ++i) {
  49. 		p[i] = n_ - i;
  50. 	}
  51.  
  52. 	return p;
  53. }
  54.  
  55. inline static void free_data(double* p_) {
  56. 	free(p_);
  57. }
  58.  
  59. inline static val_t* partition(val_t* p_left_, val_t* p_right_) {
  60.  
  61. 	val_t* const p_pivot = p_left_ + (rand32() % (p_right_ - p_left_));
  62. 	val_t tmp;
  63. 	tmp = *p_pivot; *p_pivot = *p_right_; *p_right_ = tmp;
  64.  
  65. 	val_t const* const p_prev_right = p_right_ - 1;
  66.  
  67. 	for (val_t* p = p_left_; p < p_prev_right; ++p) {
  68. 		if (*p > *p_right_) {
  69. 			tmp = *p; *p = *p_left_; *p_left_ = tmp;
  70. 			++p_left_;
  71. 		}
  72. 	}
  73. 	tmp = *p_right_; *p_right_ = *p_left_; *p_left_ = tmp;
  74. 	return p_left_;
  75. }
  76.  
  77. inline static void quickselect(val_t* p_left_, val_t* p_right_, val_t* k_) {
  78.  
  79. 	while (p_left_ < p_right_) {
  80. 		val_t* p_pivot = partition(p_left_, p_right_);
  81. 		if (p_pivot > k_) {
  82. 			p_right_ = p_pivot + 1;
  83. 		} else if (p_pivot < k_) {
  84. 			p_left_ = p_pivot + 1;
  85. 		} else {
  86. 			break;
  87. 		}
  88. 	}
  89. }
  90.  
  91. int main(int argc, char* argv[])
  92. {
  93. 	val_t* p1 = alloc_data(ELEMS);
  94. 	val_t* p2 = alloc_saiaku_data(ELEMS);
  95. 	double s;
  96. 	double e;
  97.  
  98. 	s = baka_sec_count();
  99. 	quickselect(p1, p1 + ELEMS - 1, p1 + TOPSS - 1);
  100. 	e = baka_sec_count();
  101. 	fprintf(stdout, "turnaround time ::= %.04lf sec\n", e - s);
  102.  
  103. 	s = baka_sec_count();
  104. 	quickselect(p2, p2 + ELEMS - 1, p2 + TOPSS - 1);
  105. 	e = baka_sec_count();
  106. 	fprintf(stdout, "turnaround time ::= %.04lf sec\n", e - s);
  107.  
  108. 	free_data(p1);
  109. 	free_data(p2);
  110. 	return 0;
  111. }
  112.  
Success #stdin #stdout 0.25s 157640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
turnaround time ::= 0.1077 sec
turnaround time ::= 0.0172 sec
https://ideone.com/TbWDDb
language:
C (gcc 8.3)
created:
5 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!