-
Notifications
You must be signed in to change notification settings - Fork 22
/
Spearman-s_Rank_Correlation_Coefficient.java
95 lines (81 loc) · 2.56 KB
/
Spearman-s_Rank_Correlation_Coefficient.java
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
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
// The challenging part is creating the rank arrays
// Time Complexity: O(n log n)
// Space Complexity: O(n)
public class Solution {
public static void main(String[] args) {
/* Save input */
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
double [] X = new double[size];
double [] Y = new double[size];
for (int i = 0; i < size; i++) {
X[i] = scan.nextDouble();
}
for (int i = 0; i < size; i++) {
Y[i] = scan.nextDouble();
}
scan.close();
System.out.format("%.3f", spearman(X, Y));
}
/* Calculates Spearman's rank correlation coefficient, */
private static Double spearman(double [] X, double [] Y) {
/* Error check */
if (X == null || Y == null || X.length != Y.length) {
return null;
}
/* Create Rank arrays */
int [] rankX = getRanks(X);
int [] rankY = getRanks(Y);
/* Apply Spearman's formula */
int n = X.length;
double numerator = 0;
for (int i = 0; i < n; i++) {
numerator += Math.pow((rankX[i] - rankY[i]), 2);
}
numerator *= 6;
return 1 - numerator / (n * ((n * n) - 1));
}
/* Returns a new (parallel) array of ranks. Assumes unique array values */
public static int[] getRanks(double [] array) {
int n = array.length;
/* Create Pair[] and sort by values */
Pair [] pair = new Pair[n];
for (int i = 0; i < n; i++) {
pair[i] = new Pair(i, array[i]);
}
Arrays.sort(pair, new PairValueComparator());
/* Create and return ranks[] */
int [] ranks = new int[n];
int rank = 1;
for (Pair p : pair) {
ranks[p.index] = rank++;
}
return ranks;
}
}
/* A class to store 2 variables */
class Pair {
public final int index;
public final double value;
public Pair(int i, double v) {
index = i;
value = v;
}
}
/* This lets us sort Pairs based on their value field */
class PairValueComparator implements Comparator<Pair> {
double epsilon = 0.0001; // shouldn't use " == " to compare "doubles"
@Override
public int compare(Pair p1, Pair p2) {
if (Math.abs(p1.value - p2.value) < epsilon) {
return 0;
} else if (p1.value < p2.value) {
return -1;
} else {
return 1;
}
}
}