How can i do this quicksort visualization example from p5 in Processing?

I want to do something similar in processing but it doesn’t have “async” or “await” as far i understand.

// width of each bar is taken as 8.
let values = [];
// The array 'states' helps in identifying the pivot index
// at every step, and also the subarray which is being sorted
// at any given time. 
let states = [];

// The setup() function is called once when the program 
// starts. Here, we fill the array 'values' with random values
// and the array 'states' with a value of -1 for each position.
function setup() {
  createCanvas(710, 400);
  for(let i = 0; i < width/8; i++) {
    values.push(random(height));
    states.push(-1);
  }
  quickSort(0, values.length - 1);
}

// The statements in draw() function are executed continuously
// until the program is stopped. Each statement is executed
// sequentially and after the last line is read, the first
// line is executed again.
function draw() {
  background(140);
  for(let i = 0; i < values.length; i++) {
    // color coding
    if (states[i] == 0) {
      // color for the bar at the pivot index
      fill('#E0777D');
    } else if (states[i] == 1) {
      // color for the bars being sorted currently
      fill('#D6FFB7');
    } else {
      fill(255);
    }
    rect(i * 8, height - values[i], 8, values[i]);
   }
}

async function quickSort(start, end) {
  if (start > end) {  // Nothing to sort!
    return;
  }
  // partition() returns the index of the pivot element.
  // Once partition() is executed, all elements to the  
  // left of the pivot element are smaller than it and 
  // all elements to its right are larger than it.
  let index = await partition(start, end);
  // restore original state
  states[index] = -1;
  await Promise.all(
    [quickSort(start, index - 1), 
     quickSort(index + 1, end)
    ]);
}

// We have chosen the element at the last index as 
// the pivot element, but we could've made different
// choices, e.g. take the first element as pivot.
async function partition(start, end) {
  for (let i = start; i < end; i++) {
    // identify the elements being considered currently
    states[i] = 1;
  }
  // Quicksort algorithm
  let pivotIndex = start;
  // make pivot index distinct
  states[pivotIndex] = 0;
  let pivotElement = values[end];
  for (let i = start; i < end; i++) {
    if (values[i] < pivotElement) {
      await swap(i, pivotIndex);
      states[pivotIndex] = -1;
      pivotIndex++;
      states[pivotIndex] = 0;
    }
  }
  await swap(end, pivotIndex);
  for (let i = start; i < end; i++) {
    // restore original state
    if (i != pivotIndex) {
      states[i] = -1;
    }
  }
  return pivotIndex;
}

// swaps elements of 'values' at indices 'i' and 'j'
async function swap(i, j) {
  // adjust the pace of the simulation by changing the
  // value
  await sleep(25);
  let temp = values[i];
  values[i] = values[j];
  values[j] = temp;
}

// custom helper function to deliberately slow down
// the sorting process and make visualization easy
function sleep(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

I think frameRate() can be a good substitute for those keywords in this particular case, given that the only thing they’re doing is slowing down the sketch’s execution so we can better see the sort animation:

1 Like

Hi @MarcosN,

Welcome to the forum! :wink:

Yes you are right, JavaScript support asynchronous programming out of the box and Java (Processing) has alternatives but they involve using threads or other complicated techniques.

In Processing, a way to do that is to measure time between the last event using millis() (like a counter):

int lastEventTime = 0;
int eventDuration = 1000; // Every 1s

void setup() {
  size(500, 500);
}

void draw() {
  if (millis() - lastEventTime >= eventDuration) {
    println("Event!");
    lastEventTime = millis();
  }
}

Basically you are using the draw() function as an event loop that checks if a promise is resolved.

I actually did something similar here with bubble and bogo sort (I don’t have the code anymore thought):

1 Like

Years ago I wanted to create a Java sketch that displayed various sort algorithms in action and experienced the same issues. Rather than use threads I decided on a different approach which allowed me to easily pause, change the speed or even reverse the sorting algorithm display.

The trick was to remember the actions needed to sort the data. Many sorts rely on swapping two elements in the data set so we simply need to remember which elements are swapped and the order the swaps were implemented.

This sketch is a simple demonstration of a Bubble Sort. It has two classes SwapPair which stores the indices of the two elements to be swapped and a class for the sorting algorithm. In the BubbleSort class we create an instance by passing an array of random data to the constructor which then sorts the data using the Bubble sort algorithm, remembering the swaps in an arraylist. This class has two methods forward() and reverse() which allow us to perform the next and previous swap.

The code provides a basic implementation but can easily be extended to

  • use other sorting algorithms
  • highlight the elements being swapped
  • highlight sub array ranges for instance in Quicksort
  • changing the display speed
int dir = 1;
int dw = 8; // visual width for a data element
BubbleSort bs;

void setup() {
  size(640, 320);
  textSize(16);
  textAlign(CENTER, CENTER);
  bs = new BubbleSort(randomData(width /dw, 0, height - 60));
}

float[] randomData(int n, float low, float high) {
  float[] a = new float[n];
  for (int i = 0; i < n; i++)
    a[i] = low + random(1)*(high-low);
  return a;
}

void draw() {
  background(250);
  fill(0);
  text("F = Forward        R = Reverse        P = Pause", 0, height-50, width, 40);
  stroke(64, 64, 128); fill(200, 200, 255);
  for (int i = 0; i < bs.a.length; i++)
    rect(i * dw, height-50-bs.a[i], dw, bs.a[i]);
  switch (dir) {
    case 1: bs.forward(); break;
    case -1: bs.reverse(); break;
  }
}

void keyTyped() {
  switch(key) {
    case 'f': dir = 1; break;
    case 'r': dir = -1; break;
    case 'p': dir = 0; break;
  }
}

class BubbleSort {
  float[] a;
  ArrayList<SwapPair> solution = new ArrayList<SwapPair> ();
  int idx = 0; // index to next forward swap

  BubbleSort(float[] array) {
    this.a = new float[array.length];
    arrayCopy(array, this.a);
    int n = this.a.length;
    boolean swapped = false;
    do {
      swapped = false;
      for (int i = 1; i < n; i++) {
        if (this.a[i-1] > this.a[i]) {
          this.solution.add(new SwapPair(i-1, i));
          float temp = this.a[i];
          this.a[i] = this.a[i-1];
          this.a[i-1] = temp;
          swapped = true;
        }
      }
    } while (swapped);
    // Now we have the solution restore the original array
    arrayCopy(array, this.a);
  }

  void forward() {
    if (this.idx < this.solution.size()) {
      SwapPair sw = this.solution.get(this.idx);
      float temp = this.a[sw.e0];
      this.a[sw.e0] = this.a[sw.e1];
      this.a[sw.e1] = temp;
      this.idx++;
    }
  }

  void reverse() {
    if (this.idx > 0) {
      this.idx--;
      SwapPair sw = this.solution.get(this.idx);
      float temp = this.a[sw.e0];
      this.a[sw.e0] = this.a[sw.e1];
      this.a[sw.e1] = temp;
    }
  }
}

class SwapPair {
  int e0, e1;

  SwapPair(int e0, int e1) {
    this.e0 = e0;
    this.e1 = e1;
  }
}
4 Likes

Welcome to the forum!

I formatted your code. In the future please use code formatting. It makes it easier for people to help. Thanks :slight_smile:

See the example below:

Thank you, noted. I’ll remember

1 Like

Thanks, i think i can get it done based on your code.
i’ll try to use a non recursive verions of quicksort before i do it your way just to see if i can do it and then i’ll do it like you.
I’ll post it when i’m done

If you use this technique for a recursive Quicksort then you can extend the swap pair class to include the indices of the sub-array that is being sorted. It means you can improve the visualisation ort by changing the colour behind the sub array being sorted, highlighting the recursive nature of the code.

Good luck :slight_smile:

1 Like

I can improve it further, so far it’s just an adaptation of yours but i still gotta do it for another sorting algorithm and then i want to do more detailed visualization like you suggested.

import java.lang.*;
int idx =0;
int dir = 0;
int dw = 15; // visual width for a data element
int[] arr;
int[] base;

ArrayList<SwapPair> solution = new ArrayList<SwapPair> ();

void setup() {
  size(1000, 800);
  textSize(16);
  textAlign(CENTER, CENTER);
   arr = randomData(width /dw, 0, height - 60);
   //base = randomData(width /dw, 0, height - 60);
  //base = arr;
    //for (int i=0; i < arr.length; i++) base[i]=arr[i];   
   //    arrayCopy(base, arr);   
   
   //solution.add(new SwapPair(5, 0));
   quickSortIterative(arr, 0, arr.length - 1);  
   for (int i = 0; i < solution.size(); i++){
      forward();
   }
   
}

class SwapPair {
  int e0, e1;

  SwapPair(int e0, int e1) {
    this.e0 = e0;
    this.e1 = e1;
  }
}

int[] randomData(int n, int low, int high) {
  int[] a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = (int)(low + random(1)*(high-low));
  return a;
}



void draw() {
  background(250);
  fill(0);
  text("F = Forward        R = Reverse        P = Pause", 0, height-50, width, 40);
  stroke(64, 64, 128); fill(200, 200, 255);
  for (int i = 0; i < arr.length; i++)
    rect(i * dw, height-50-arr[i], dw, arr[i]);
  switch (dir) {
    case 1: forward(); break;
    case -1: reverso(); break;
  }
}


void keyTyped() {
  switch(key) {
    case 'r': dir = 1; break;
    case 'f': dir = -1; break;
    case 'p': dir = 0; break;
  }
}



  int partition(int p[], int low, int high){
      int pivot = arr[high];
      // index of smaller element
      int i = (low - 1);
      for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot) {
          i++;
          // swap arr[i] and arr[j]
          solution.add(new SwapPair(i, j));
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
      }
  
      // swap arr[i+1] and arr[high] (or pivot)
      int temp = arr[i + 1];
      arr[i + 1] = arr[high];
      arr[high] = temp;
      solution.add(new SwapPair(i+1, high));
  
      return i + 1;
  }

  /* A[] --> Array to be sorted,
l --> Starting index,
h --> Ending index */
  void quickSortIterative(int arr[], int l, int h)
  {
    // Create an auxiliary stack
    int[] stack = new int[h - l + 1];

    // initialize top of stack
    int top = -1;

    // push initial values of l and h to stack
    stack[++top] = l;
    stack[++top] = h;

    // Keep popping from stack while is not empty
    while (top >= 0) {
      // Pop h and l
      h = stack[top--];
      l = stack[top--];

      // Set pivot element at its correct position
      // in sorted array
      int p = partition(arr, l, h);

      // If there are elements on left side of pivot,
      // then push left side to stack
      if (p - 1 > l) {
        stack[++top] = l;
        stack[++top] = p - 1;
      }

      // If there are elements on right side of pivot,
      // then push right side to stack
      if (p + 1 < h) {
        stack[++top] = p + 1;
        stack[++top] = h;
      }
    }
  }
  
  
  void forward() {
    if (idx < solution.size()) {
      SwapPair sw = solution.get(this.idx);
      int temp = arr[sw.e0];
      arr[sw.e0] = arr[sw.e1];
      arr[sw.e1] = temp;
      idx++;
    }
  }

  void reverso() {
    if (idx > 0) {
      
      idx--;
      SwapPair sw =solution.get(idx);
      int temp = arr[sw.e0];
      arr[sw.e0] = arr[sw.e1];
      arr[sw.e1] = temp;
      
    }
  }

Turns out this is not right. The sorting works out but if i rewind it does not behave correctly

I just tried out the code above and it worked fine for me. I took a snapshot of the graph before sorting and then did several forwards, pauses and reverses before finally letting it reverse back to the original state. The output and the snapshot were exactly the same.

In what way does

Sorry, so much has changed!
Now i need to make a visualization for mergesort and i’m having a way harder time because of the nature of it’s temporary arrays.
What we were originally talking about ended up becoming this code.
It fails if you try to use B command when it’s already at the start, is screws up the order, but is serviceable.

i made a whole new topic about it.

import java.lang.*;
int pos = 0;
int dir = 0;
int largura = 20;
//int[] arr = {5,8,15,20,17,14,55,100,11,5,6,67,8,4,12,13,1,47,5,27,38,5,7,50,47,84,9,33,41};
//int[] arr = {60,20,45,100,5,80};
int[] arr;
int[] base;

ArrayList<TrocaPos> solution = new ArrayList<TrocaPos> ();

void setup() {
  size(1000, 800);
  textSize(16);
  textAlign(CENTER, CENTER);
   arr = numeros(width /largura, 0, height - 60);
   base = numeros(width /largura, 0, height - 60);
   arrayCopy(arr, base);
   //quickSortIterative(arr, 0, arr.length - 1);
   QuickSort(arr, 0, arr.length - 1);
   arrayCopy(base, arr);  
}

class TrocaPos {
  int t0, t1;

  TrocaPos(int t0, int t1) {
    this.t0 = t0;
    this.t1 = t1;
  }
}

int[] numeros(int n, int low, int high) {
  int[] a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = (int)(low + random(1)*(high-low));
  return a;
}

void draw() {
  background(250);
  fill(0);
  text("F = Forward      P = Pause      R = Reverse      V = volta um passo     B = vai um passo", 0, height-60, width, 45);
  text(pos, 15,15);
  stroke(50, 50, 100);
  fill(200, 200, 250);
  for (int i = 0; i < arr.length; i++){
    rect(i * largura, height-50-arr[i], largura, arr[i]);    
  }
  switch (dir) {
    case 1: Forward(); break;
    case -1: reverso(); break;
    case 2:  if(pos>0){pos--;ForwardStep();}break;
    case -2:  if(pos < solution.size()){reversoS();pos++;}break;
  }
}

void keyTyped() {
  switch(key) {
    case 'f': dir = 1; break;
    case 'r': dir = -1; break;
    case 'p': dir = 0; break;
    case 'v': dir = 2; break;
    case 'b': dir = -2;  break;
  }
}

int corta(int p[], int low, int high){
    int pivot = arr[high];    
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
      if (arr[j] <= pivot) {
        i++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        solution.add(new TrocaPos(j, i));
      }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    solution.add(new TrocaPos( i+1, high));
    return i + 1;
}

void QuickSort(int arr[], int low, int high)
{
  if (low < high) {
      int pi = corta(arr, low, high);
      QuickSort(arr, low, pi - 1);
      QuickSort(arr, pi + 1, high);
  }
}

void Forward() {
  if (pos < solution.size()) {
    TrocaPos sw = solution.get(pos);
    int temp = arr[sw.t0];
    arr[sw.t0] = arr[sw.t1];
    arr[sw.t1] = temp;
    pos++;
  }
}

void reverso() {
  if (pos > 0) {
    pos--;
    TrocaPos sw =solution.get(pos);
    int temp = arr[sw.t0];
    arr[sw.t0] = arr[sw.t1];
    arr[sw.t1] = temp;    
  }  
}
  
void ForwardStep() {
  if (pos < solution.size()) {
    TrocaPos sw = solution.get(pos);
    int temp = arr[sw.t0];
    arr[sw.t0] = arr[sw.t1];
    arr[sw.t1] = temp;     
  }
  dir = 0;
}

void reversoS() {
  if (pos > 0) {
    TrocaPos sw =solution.get(pos);
    int temp = arr[sw.t0];
    arr[sw.t0] = arr[sw.t1];
    arr[sw.t1] = temp;    
  }
  dir = 0;
}

/*
void quickSortIterative(int arr[], int l, int h)
{
  int[] stack = new int[h - l + 1];
  int top = -1;

  // push initial values of l and h to stack
  stack[++top] = l;
  stack[++top] = h;

  // Keep popping from stack while is not empty
  while (top >= 0) {
    // Pop h and l
    h = stack[top--];
    l = stack[top--];

    // Set pivot element at its correct larguraition
    // in sorted array
    int p = corta(arr, l, h);

    // If there are elements on left side of pivot,
    // then push left side to stack
    if (p - 1 > l) {
      stack[++top] = l;
      stack[++top] = p - 1;
    }

    // If there are elements on right side of pivot,
    // then push right side to stack
    if (p + 1 < h) {
      stack[++top] = p + 1;
      stack[++top] = h;
    }
  }
}
*/