fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <random>
  4. #include <chrono>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int partition_random(int a[], int p, int r);
  10.  
  11. int partition(int a[], int p, int r) {
  12.  int t = a[r];
  13.  int i = p - 1;
  14.  for (int j = p; j < r;j++){
  15.   if (a[j] <= t) {
  16.    i += 1;
  17.    std::swap(a[i], a[j]);
  18.   }
  19.  }
  20.  std::swap(a[i + 1], a[r]);
  21.  return i + 1;
  22. }
  23.  
  24. int quick_select(int a[], int s, int n, int k) {
  25.   int r = partition_random(a, s, n);
  26.   if (r - s == k - 1) {return a[r];}
  27.   else {
  28.  
  29.   if (k - 1 < r - s) {
  30.    return quick_select(a, s, r - 1, k);
  31.   }
  32.   else  {
  33.    return quick_select(a, r + 1 , n, k - r + s - 1);
  34.   }
  35.  }
  36. }
  37.  
  38. int partition_random(int a[], int p, int r) {
  39.  std::random_device rd;     
  40.  std::mt19937 rng(rd());   
  41.  std::uniform_int_distribution<int> uni(p, r); 
  42.  auto rn = uni(rng);
  43.  std::swap(a[r], a[rn]);
  44.  return partition(a, p, r);
  45. }
  46.  
  47. float median(int a [], int n) {
  48.  if (n % 2 == 1)
  49.   return quick_select(a, 0, n - 1, n / 2 + 1);
  50.  int l = n / 2;
  51.  int r = n / 2 + 1;
  52.  return (1.0 * (quick_select(a, 0, n - 1, l) + 
  53.    quick_select(a, 0, n - 1, r))) / 2;
  54. }
  55.  
  56. int main() {
  57. 	 unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  58.  
  59. 	const int size = 5;
  60. 	int am[size] {-2, -2, 1, 0, -1};
  61.  
  62. /*
  63.     srand(seed);
  64.  
  65. 	for(int i=0; i < size; i++) {
  66. 	   am[i] = (rand() % size) - (size/2); 	
  67. 	}
  68. */
  69.  
  70. 	int expectedVal = -1;
  71.  
  72. 	for(int i=0; i < size * 2; i++) {
  73. 	  	shuffle (am, am + size, std::default_random_engine(seed));
  74. 	  	cout << "-- array: ";
  75.      	for(int j=0; j < size; j++) {
  76.      		cout << " " << am[j];
  77.      	}
  78.      	cout << "\n";
  79.  
  80. 	  	float med = median(am, size);
  81. 	  	cout << "median: " << med << ", ok? " << (med == expectedVal ? "T": "F") << "\n";
  82. 	}
  83.  
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-- array:  1 -1 0 -2 -2
median: -1, ok? T
-- array:  -1 1 0 -2 -2
median: -1, ok? T
-- array:  -1 1 0 -2 -2
median: -1, ok? T
-- array:  -1 0 1 -2 -2
median: -1, ok? T
-- array:  -1 1 0 -2 -2
median: -1, ok? T
-- array:  -1 0 1 -2 -2
median: -1, ok? T
-- array:  -1 1 0 -2 -2
median: -1, ok? T
-- array:  -1 0 1 -2 -2
median: -1, ok? T
-- array:  -1 1 0 -2 -2
median: -1, ok? T
-- array:  -1 0 1 -2 -2
median: -1, ok? T
https://ideone.com/D4ZZQ5
language:
C++14 (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!