# Quicksort visualization

I’m trying to write a quicksort visualization, but the sorting happens too fast.

``````float[] values;

void swap(float[] arr, int a, int b) {
float temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;

// delay(1);
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);
}
}

void setup() {
size(800, 600);
values = new float[width];
for (int i = 0; i < values.length; i++) {
values[i] = random(0, height);
}
}

void draw() {
background(0);
for (int i = 0; i < values.length; i++) {
stroke(255);
line(i, height, i, height - values[i]);
}
quickSort(values, 0, values.length - 1);
}
``````

I’m trying to redraw the array every time a swap is made, and I have done this but it’s way too fast and I would like to add a delay.`Preformatted text`

2 Likes

-a- please repair above code posting

• 1- show us a complete ( running ) example of your problem
• 2- paste it into the
`</> formatted text`

-b- the draw loop is supposed to run 60 times per sec unless use
https://processing.org/reference/frameRate_.html

-c- a drawing is prepared inside draw() and shown after it,
so draw a line and call redraw produces?

-d- to show something in STEPS
must use a global variable
iterated in every draw loop.
( again the frequency will be the framerate )

1 Like

The problem is that the `quicksort()` function sorts it competly, and by calling it inside`draw()` 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;
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
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

This is what you need to do

1. Create a backup copy of the array to sort so you have a copy of the start positions.
2. Perform the quicksort but as it executes remember the array indices for each swap. Use a list because you don’t know how many swaps you need in advance
3. Restore your array to its original state by copying the backup
4. Now using the start positions and the list of swaps you can observe the sort at any pace you like, including going backwards.
2 Likes

The central issue is this: `draw()` is already a for loop. Each time `draw()` runs, the screen updates. So if you want to animate each step of the sort, you need to make each step run once with each `draw()`.

There is a great detailed discussion of this for insertionSort, using examples, here:

It shows two approaches – to put it in a thread or to put it in a class. However you can also just do the class-based approach with no class – global variables and the code in draw().

2 Likes

I had forgotten that back in 2014 I created a sort algorithm visualiser that used this approach, I even created a video for it. The sketch shows 13 different sort algorithms which could be used with different size data sets and includes the infamous quicksort median of three killer data set. You might try the standard quicksort algorithm on a sorted data set - so slow the bubble sort is faster.

Anyway here is the video and if you want to download the sketch I can make it available but I understand if you want the challenge and satisfaction of doing it yourself. 4 Likes

I would love to see that sketch. Better to have that than to keep having to raise questions like this

You can download the sketch here. It runs in Java mode and requires G4P to be installed.

1 Like

Thanks for sharing! And befitting sketch name 