91 lines
2.2 KiB
Plaintext
91 lines
2.2 KiB
Plaintext
final int amount = 20;
|
|
final float twoThirds = (2/3f);
|
|
|
|
ArrayList<Integer> bars = new ArrayList<Integer>();
|
|
boolean finished = false;
|
|
Job stoogeSort;
|
|
float barWidth;
|
|
|
|
void setup() {
|
|
fullScreen();
|
|
frameRate(144);
|
|
|
|
textAlign(LEFT, TOP);
|
|
textSize(32);
|
|
|
|
|
|
barWidth = (float)width / amount;
|
|
for (int i = 0; i < amount; i++)
|
|
bars.add(round(random(height * 0.1, height * 0.9)));
|
|
|
|
stoogeSort = new Job(0, bars.size()-1);
|
|
}
|
|
|
|
void draw() {
|
|
background(0);
|
|
|
|
for (int i = 0; i < amount; i++) {
|
|
final int barHeight = bars.get(i);
|
|
fill(255);
|
|
if (stoogeSort.contains(i) && !finished)
|
|
fill(0,255,0);
|
|
rect(i * barWidth, height - barHeight, barWidth, barHeight);
|
|
}
|
|
|
|
fill(255);
|
|
text("Bar Amount: "+amount+"; Queue Length: "+stoogeSort.getLength()+"; FPS: "+round(frameRate), 0, 0);
|
|
|
|
if (!finished)
|
|
finished = stoogeSort.work();
|
|
}
|
|
|
|
class Job {
|
|
int section1end, section2start, start, end;
|
|
ArrayList<Job> children = new ArrayList<Job>();
|
|
|
|
Job(int s, int e) {
|
|
start = s;
|
|
end = e;
|
|
if (!(s+1 == e)) {
|
|
final int k = floor((end-start+1)/3f);
|
|
children.add(new Job(start, end-k));
|
|
children.add(new Job(start+k, end));
|
|
children.add(new Job(start, end-k));
|
|
}
|
|
}
|
|
|
|
boolean work() {
|
|
final boolean check = children.size() > 0;
|
|
if (check) {
|
|
final boolean fin = children.get(0).work();
|
|
if (fin)
|
|
children.remove(0);
|
|
if (children.size() == 0)
|
|
return true;
|
|
} else {
|
|
final int st = bars.get(start);
|
|
final int et = bars.get(end);
|
|
if (st > et) {
|
|
bars.set(start, et);
|
|
bars.set(end, st);
|
|
}
|
|
}
|
|
return !check;
|
|
}
|
|
|
|
boolean contains(int i) {
|
|
if (children.size() > 0)
|
|
return children.get(0).contains(i);
|
|
return start == i || end == i;
|
|
}
|
|
|
|
int getLength() {
|
|
if (children.size() > 0) {
|
|
int sum = 0;
|
|
for (Job c : children)
|
|
sum += c.getLength();
|
|
return sum;
|
|
}
|
|
return 1;
|
|
}
|
|
} |