-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathTwoWaysAlgoVisualizer.java
117 lines (85 loc) · 2.97 KB
/
TwoWaysAlgoVisualizer.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import java.awt.*;
public class TwoWaysAlgoVisualizer {
private static int DELAY = 20;
private TwoWaysQuickSortData data;
private TwoWaysAlgoFrame frame;
public TwoWaysAlgoVisualizer(int sceneWidth, int sceneHeight, int N, TwoWaysQuickSortData.Type dataType) {
// 初始化数据
data = new TwoWaysQuickSortData(N, sceneHeight, dataType);
// 初始化视图
EventQueue.invokeLater(() -> {
frame = new TwoWaysAlgoFrame("Two Ways Quick Sort Visualization", sceneWidth, sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
public TwoWaysAlgoVisualizer(int sceneWidth, int sceneHeight, int N) {
this(sceneWidth, sceneHeight, N, TwoWaysQuickSortData.Type.Default);
}
public void run() {
setData(-1, -1, -1, -1, -1, -1);
quickSort2Ways(0, data.N() - 1);
setData(-1, -1, -1, -1, -1, -1);
}
private void quickSort2Ways(int l, int r) {
if (l > r)
return;
if (l == r) {
setData(l, r, l, -1, -1, -1);
return;
}
setData(l, r, -1, -1, -1, -1);
int p = partition(l, r);
quickSort2Ways(l, p - 1);
quickSort2Ways(p + 1, r);
}
private int partition(int l, int r) {
int p = (int) (Math.random() * (r - l + 1)) + l;
setData(l, r, -1, p, -1, -1);
data.swap(l, p);
int v = data.get(l);
setData(l, r, -1, l, -1, -1);
// arr[l+1...i) <= v; arr(j...r] >= v
int i = l + 1, j = r;
setData(l, r, -1, l, i, j);
while (true) {
while (i <= r && data.get(i) < v) {
i++;
setData(l, r, -1, l, i, j);
}
while (j >= l + 1 && data.get(j) > v) {
j--;
setData(l, r, -1, l, i, j);
}
if (i > j)
break;
data.swap(i, j);
i++;
j--;
setData(l, r, -1, l, i, j);
}
data.swap(l, j);
setData(l, r, j, -1, -1, -1);
return j;
}
private void setData(int l, int r, int fixedPivot, int curPivot, int curL, int curR) {
data.l = l;
data.r = r;
if (fixedPivot != -1)
data.fixedPivots[fixedPivot] = true;
data.curPivot = curPivot;
data.curL = curL;
data.curR = curR;
frame.render(data);
AlgoVisHelper.pause(DELAY);
}
public static void main(String[] args) {
int sceneWidth = 800;
int sceneHeight = 800;
int N = 100;
TwoWaysAlgoVisualizer vis = new TwoWaysAlgoVisualizer(sceneWidth, sceneHeight, N, TwoWaysQuickSortData.Type.Default);
// AlgoVisualizer vis = new AlgoVisualizer(sceneWidth, sceneHeight, N, TwoWaysQuickSortData.Type.NearlyOrdered);
// AlgoVisualizer vis = new AlgoVisualizer(sceneWidth, sceneHeight, N, TwoWaysQuickSortData.Type.Identical);
}
}