quick sort

qsort.pde

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");
}