Quicksort visualization

Processing Coding Questions
3

The problem is that the quicksort() function sorts it competly, and by calling it insidedraw() you are sorting the entire list of values completely every frame, even if you are calling redraw().
A way to achieve what you want with minimal edits and without changing how the sort is performed is to use a multithreaded approach like so:

float[] values;

void swap(float[] arr, int a, int b) {
  float temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
  try{Thread.sleep(10);}catch(Exception e){}; //delay the thread operating this function
  redraw();
  
}

int partition(float[] arr, int start, int end) {
  int pivotIndex = start;
  float pivotValue = arr[end];
  for (int i =start; i < end; i++) {
    if (arr[i] < pivotValue) {
      swap(arr, i, pivotIndex++);
      // pivotIndex++;
    }
  }
  swap(arr, pivotIndex, end);
  return pivotIndex;
}

void quickSort(float[] arr, int start, int end) {
  if (start < end) {
    int index = partition(arr, start, end);
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end);
  }
}

//make a thread and override the run to perform the sort instead
Thread t = new Thread(){
  public void run(){
    quickSort(values, 0, values.length - 1);
  }
};

void setup() {
  size(800, 600);
  values = new float[width];
  for (int i = 0; i < values.length; i++) {
    values[i] = random(0, height);
  }
  t.start(); //start the thread after array is populated
}

void draw() {
  background(0);
  for (int i = 0; i < values.length; i++) {
    stroke(255);
    line(i, height, i, height - values[i]);
  }
  //remove this quicksort call here bc its now done in the thread - in parralel to the sketch.
}
2 Likes