-
-
Notifications
You must be signed in to change notification settings - Fork 1.5k
Expand file tree
/
Copy pathSort.java
More file actions
46 lines (35 loc) · 911 Bytes
/
Sort.java
File metadata and controls
46 lines (35 loc) · 911 Bytes
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
package processing.data;
/**
* Internal sorter used by several data classes.
* Advanced users only, not official API.
*/
public abstract class Sort implements Runnable {
public Sort() { }
public void run() {
int c = size();
if (c > 1) {
sort(0, c - 1);
}
}
protected void sort(int i, int j) {
int pivotIndex = (i+j)/2;
swap(pivotIndex, j);
int k = partition(i-1, j);
swap(k, j);
if ((k-i) > 1) sort(i, k-1);
if ((j-k) > 1) sort(k+1, j);
}
protected int partition(int left, int right) {
int pivot = right;
do {
while (compare(++left, pivot) < 0) { }
while ((right != 0) && (compare(--right, pivot) > 0)) { }
swap(left, right);
} while (left < right);
swap(left, right);
return left;
}
abstract public int size();
abstract public int compare(int a, int b);
abstract public void swap(int a, int b);
}