1 /*
2 * Copyright (C) 2021 Jakub Kruszona-Zawadzki, Core Technology Sp. z o.o.
3 *
4 * This file is part of MooseFS.
5 *
6 * MooseFS is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, version 2 (only).
9 *
10 * MooseFS is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with MooseFS; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02111-1301, USA
18 * or visit http://www.gnu.org/licenses/gpl-2.0.html
19 */
20
21 #ifndef _MEDIAN_H_
22 #define _MEDIAN_H_
23
24 #include <inttypes.h>
25
median_find(double * array,uint32_t n)26 static inline double median_find(double *array, uint32_t n) {
27 int32_t l,r,c,m,i,j;
28 double tmp;
29
30 l = 0;
31 r = n-1;
32 m = (l+r)/2;
33 for (;;) {
34 if (r<=l) {
35 return array[m];
36 }
37 if ((r-l)==1) {
38 if (array[l] > array[r]) {
39 tmp = array[l];
40 array[l] = array[r];
41 array[r] = tmp;
42 }
43 return array[m];
44 }
45 c = (l+r)/2;
46 if (array[c] > array[r]) {
47 tmp = array[c];
48 array[c] = array[r];
49 array[r] = tmp;
50 }
51 if (array[l] > array[r]) {
52 tmp = array[l];
53 array[l] = array[r];
54 array[r] = tmp;
55 }
56 if (array[c] > array[l]) {
57 tmp = array[c];
58 array[c] = array[l];
59 array[l] = tmp;
60 }
61 i = l+1;
62 j = r;
63 tmp = array[c];
64 array[c] = array[i];
65 array[i] = tmp;
66 for (;;) {
67 do {
68 i++;
69 } while (array[l] > array[i]);
70 do {
71 j--;
72 } while (array[j] > array[l]);
73 if (j<i) {
74 break;
75 }
76 tmp = array[i];
77 array[j] = array[i];
78 array[j] = tmp;
79 }
80 tmp = array[l];
81 array[l] = array[j];
82 array[j] = tmp;
83
84 if (j<=m) {
85 l = i;
86 }
87 if (j>=m) {
88 r = j-1;
89 }
90 }
91 }
92
93 #endif
94