Skip to content

Instantly share code, notes, and snippets.

@likr
Created June 8, 2020 10:37
Show Gist options
  • Save likr/a479431a1177b78de36b22d1237ca7d0 to your computer and use it in GitHub Desktop.
Save likr/a479431a1177b78de36b22d1237ca7d0 to your computer and use it in GitHub Desktop.
quick sort
void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
void qsort(int[] a, int start, int stop) {
if (stop - start <= 1) {
return;
}
swap(a, start, int(random(start, stop - start)));
int left = 0;
for (int i = start + 1; i < stop; ++i) {
if (a[i] <= a[start]) {
swap(a, start + 1 + left, i);
left += 1;
}
}
swap(a, start, start + left);
qsort(a, start, start + left);
qsort(a, start + left + 1, stop);
}
void setup() {
noLoop();
}
void draw() {
for (int k = 0; k < 1000; ++k) {
int[] a = new int[1000];
for (int i = 0; i < a.length; ++i) {
a[i] = int(random(100000));
}
qsort(a, 0, a.length);
for (int i = 1; i < a.length; ++i) {
if (a[i - 1] > a[i]) {
println("error");
}
}
}
println("finish");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment