Floyd-Rivest-algorithm/floyd-rivest.c at main · ManosPapadakis95/Floyd-Rivest-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include "floyd-rivest.h"


// left is the left index for the interval
// right is the right index for the interval
// k is the desired index value, where obj[k] is the (k+1)th smallest element when left = 0
void ipartition(int obj[],int left,int right,int k,Func_int cmp){
  int tmp;
  while (right > left) {
    // Use select recursively to sample a smaller set of size s
    // the arbitrary constants 600 and 0.5 are used in the original
    // version to minimize execution time.
    if (right - left > 600){
      int n = right - left + 1;
      int i = k - left + 1;
      double z = log(n);
      double s = 0.5 * exp(2 * z/3);
      double sd = 0.5 * sqrt(z * s * (n - s)/n) * sgn(i - n/2);
      int newLeft = max(left, int(k - i * s/n + sd));
      int newRight = min(right, int(k + (n - i) * s/n + sd));
      ipartition(obj, newLeft, newRight, k,cmp);
    }
    // partition the elements between left and right around t
    int t = obj[k] ;
    int i = left;
    int j = right;
    swap(obj[left] , obj[k]);
    if (cmp(obj[right] , t)>0) {
      swap (obj[right] , obj[left]);
    }
    while (i < j) {
      swap (obj[i] , obj[j]);
      ++i;
      --j;
      for (;cmp(obj[i],t) < 0;++i);
      for (;cmp(obj[j],t) > 0;--j);
    }
    if (cmp(obj[left] , t)==0) {
      swap (obj[left] , obj[j]);
    }
    else{
      ++j;
      swap (obj[j] , obj[right]);
    }
    // Adjust left and right towards the boundaries of the subset
    // containing the (k - left + 1)th smallest element.
    if (j <= k)
      left = j + 1;
    if (k <= j)
      right = j - 1;
  }
}

// left is the left index for the interval
// right is the right index for the interval
// k is the desired index value, where obj[k] is the (k+1)th smallest element when left = 0
void dpartition(double obj[],int left,int right,int k,Func_double cmp){
  double tmp;
  while (right > left) {
    // Use select recursively to sample a smaller set of size s
    // the arbitrary constants 600 and 0.5 are used in the original
    // version to minimize execution time.
    if (right - left > 600){
      int n = right - left + 1;
      int i = k - left + 1;
      double z = log(n);
      double s = 0.5 * exp(2 * z/3);
      double sd = 0.5 * sqrt(z * s * (n - s)/n) * sgn(i - n/2);
      int newLeft = max(left, int(k - i * s/n + sd));
      int newRight = min(right, int(k + (n - i) * s/n + sd));
      dpartition(obj, newLeft, newRight, k,cmp);
    }
    // partition the elements between left and right around t
    double t = obj[k] ;
    int i = left;
    int j = right;
    swap(obj[left] , obj[k]);
    if (cmp(obj[right] , t)>0) {
      swap (obj[right] , obj[left]);
    }
    while (i < j) {
      swap (obj[i] , obj[j]);
      ++i;
      --j;
      for (;cmp(obj[i],t) < 0;++i);
      for (;cmp(obj[j],t) > 0;--j);
    }
    if (cmp(obj[left] , t)==0) {
      swap (obj[left] , obj[j]);
    }
    else{
      ++j;
      swap (obj[j] , obj[right]);
    }
    // Adjust left and right towards the boundaries of the subset
    // containing the (k - left + 1)th smallest element.
    if (j <= k)
      left = j + 1;
    if (k <= j)
      right = j - 1;
  }
}

int inth(int obj[],int k,int left,int right, Func_int cmp){
  ipartition(obj,left,right,k,cmp);
  return obj[k-left+1];
}
double dnth(double obj[],int k,int left,int right, Func_double cmp){
  dpartition(obj,left,right,k,cmp);
  return obj[k-left+1];
}