SortingAlgorithms/QuickSort/QuickSort.pde

final float timeout = 2;

ArrayList<Integer> bars = new ArrayList<Integer>();
ArrayList<Job> queue = new ArrayList<Job>();
int mQL = 1, aQL = 0, amount = 100;
float barWidth = 10f;

int sortedFrameCountCapture = -1;

void init() {
  amount = floor(random(100, 750));
  barWidth = (float)width / amount;
  bars = new ArrayList<Integer>();
  for (int i = 0; i < amount; i++) {
    // bars.add(round(map(i,0,amount-1,0,width/2)));
    // bars.add(round(random(width/2)));
    bars.add(round(random(height * 0.1, height * 0.9)));
  }
  // int counter = 0;
  // while (counter < 2*amount) {
  //   int i = floor(random(bars.size()));
  //   int j = floor(random(bars.size()));
  //   int t = bars.get(i);
  //   bars.set(i, bars.get(j));
  //   bars.set(j, t);
  //   counter++;
  // }
}

void setup() {
  fullScreen(P2D);
  // size(1280, 720);

  init();
  queue.add(new Job(0, amount-1));
  
  frameRate(amount);
}

void draw() {
  background(0);

  noStroke();
  stroke(0);
  for (int i = 0; i < bars.size(); i++) {
    // stroke(255);
    fill(255);
    for (int j = 0; j < queue.size(); j++) {
      Job job = queue.get(j);
      if (i == job.rightIndex || i == job.leftIndex) {
        // stroke(255, 0, 0);
        fill(255, 0, 0);
      } else if (i == job.i) {
        // stroke(0, 255, 0);
        fill(0, 255, 0);
      } else if (i == job.j) {
        // stroke(0, 0, 255);
        fill(0, 0, 255);
      }
    }
    // line(i, height, i, height-bars.get(i));
    rect(i * barWidth, height, barWidth, -bars.get(i));
    // ellipse(i * barWidth + barWidth / 2, height - bars.get(i), barWidth, barWidth);
    // final float a = map(i, 0, bars.size()-1, 0, 12*TWO_PI);
    // final float r = bars.get(i);
    // final float x = width/2 + cos(a) * r;
    // final float y = height/2 + sin(a) * r;
    // ellipse(x, y, barWidth, barWidth);
  }

  /*if (queue.size() > 0) {
    queue.get(0).sortStep();
  }*/
  for (int i = 0; i < queue.size(); i++) {
    queue.get(i).sortStep();
  }
  
  if (queue.size() == 0) {
    if (sortedFrameCountCapture == -1) {
      sortedFrameCountCapture = frameCount;
    } else if (frameCount-sortedFrameCountCapture>=round(frameRate*timeout)) {
      sortedFrameCountCapture = -1;
      
      init();
      queue.add(new Job(0, amount-1));
      
      mQL = 1;
      aQL = 0;
      
      frameRate(amount);
    }
  }

  mQL = max(queue.size(), mQL);

  fill(255,0,0);
  stroke(255,0,0);
  textAlign(LEFT, TOP);
  textSize(width*0.022);
  text("Queue Length: "+queue.size()+"; Max. Length: "+mQL+"; Absolute Length: "+aQL+"; Bar Amount: "+bars.size()+"; FPS: "+round(frameRate)+";", 0, 0);
}

class Job {
  int leftIndex, rightIndex;
  int i, j, pivotValue;
  boolean iIndex, jIndex;

  Job(int start, int end) {
    i = start;
    j = end - 1;
    rightIndex = end;
    leftIndex = start;
    pivotValue = bars.get(rightIndex);
  }

  void sortStep() {
    checkIndecies();
    if (i < j || iIndex || jIndex) {
      if (iIndex) {
        i++;
      } else if (jIndex) {
        j--;
      } else if (i < j) {
        final int tV1 = bars.get(i);
        bars.set(i, bars.get(j));
        bars.set(j, tV1);
      }
    } else {
      // Reverse here for reverse sorting-order
      if (bars.get(i) > pivotValue) {
        final int tV2 = bars.get(i);
        bars.set(i, bars.get(rightIndex));
        bars.set(rightIndex, tV2);
      }

      if (isInBounds(i-1) && (leftIndex < i-1)) {
        queue.add(new Job(leftIndex, i-1));
      }
      if (isInBounds(i+1) && (i+1 < rightIndex)) {
        queue.add(new Job(i+1, rightIndex));
      }
      aQL++;
      queue.remove(this);
    }
  }

  void checkIndecies() {
    // Reverse here for reverse sorting-order
    iIndex = (i < rightIndex) && (bars.get(i) < pivotValue);
    jIndex = (j > leftIndex) && (bars.get(j) >= pivotValue);
  }

  boolean isEqual(Job other) {
    return ((other.leftIndex == leftIndex) && (other.rightIndex == rightIndex));
  }
}

boolean isInBounds(int index) {
  return ((index >= 0) && (index < bars.size()));
}