# Quicksort visualization

**URL:** <https://discourse.processing.org/t/quicksort-visualization/14120>\
**Category:** Coding Questions\
**Created:** [September 22, 2019, 9:44pm UTC](https://discourse.processing.org/t/quicksort-visualization/14120 "2019-09-22T21:44:56Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![hawko](https://avatars.discourse-cdn.com/v4/letter/h/e8c25b/32.png) [@hawko](https://discourse.processing.org/u/hawko)\
**Post date:** [September 22, 2019, 9:44pm UTC](https://discourse.processing.org/t/quicksort-visualization/14120/1 "2019-09-22T21:44:57Z")

</div>

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

```auto
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`

---

<div class="post-metadata">

**Author:** ![kll](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/kll/32/964_2.png) [@kll](https://discourse.processing.org/u/kll)\
**Post date:** [September 23, 2019, 1:44am UTC](https://discourse.processing.org/t/quicksort-visualization/14120/2 "2019-09-23T01:44:40Z")

</div>

-a- please repair above code posting

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

-b- the draw loop is supposed to run 60 times per sec unless use  
[https://processing.org/reference/frameRate\_.html](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 )

---

<div class="post-metadata">

**Author:** ![Xelo](https://avatars.discourse-cdn.com/v4/letter/x/9fc348/32.png) [@Xelo](https://discourse.processing.org/u/Xelo)\
**Post date:** [September 23, 2019, 3:02am UTC](https://discourse.processing.org/t/quicksort-visualization/14120/3 "2019-09-23T03:02:26Z")

</div>

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:

```auto
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.
}

```

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 23, 2019, 8:20am UTC](https://discourse.processing.org/t/quicksort-visualization/14120/4 "2019-09-23T08:20:49Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [September 24, 2019, 7:08pm UTC](https://discourse.processing.org/t/quicksort-visualization/14120/5 "2019-09-24T19:08:53Z")

</div>

> [@hawko](#):
>
> the sorting happens too fast

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:

- [Updating outside of draw() - Processing 2.x and 3.x Forum](https://forum.processing.org/two/discussion/21696/updating-outside-of-draw)

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().

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 26, 2019, 6:16pm UTC](https://discourse.processing.org/t/quicksort-visualization/14120/6 "2019-09-26T18:16:18Z")

</div>

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. 😁

[![](https://img.youtube.com/vi/ezMDe0b_3c0/hqdefault.jpg "Bubble Sort") ](https://www.youtube.com/watch?v=ezMDe0b_3c0)

---

<div class="post-metadata">

**Author:** ![hawko](https://avatars.discourse-cdn.com/v4/letter/h/e8c25b/32.png) [@hawko](https://discourse.processing.org/u/hawko)\
**Post date:** [September 27, 2019, 3:11am UTC](https://discourse.processing.org/t/quicksort-visualization/14120/7 "2019-09-27T03:11:03Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 27, 2019, 11:46am UTC](https://discourse.processing.org/t/quicksort-visualization/14120/8 "2019-09-27T11:46:32Z")

</div>

You can download the sketch [here](http://lagers.org.uk/zzz/AllSortsOfSorts-190927a.zip). It runs in Java mode and requires G4P to be installed.

---

<div class="post-metadata">

**Author:** ![Tiemen](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/tiemen/32/5477_2.png) [@Tiemen](https://discourse.processing.org/u/Tiemen)\
**Post date:** [September 28, 2019, 1:36pm UTC](https://discourse.processing.org/t/quicksort-visualization/14120/9 "2019-09-28T13:36:46Z")

</div>

Thanks for sharing! And befitting sketch name 😉

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 28, 2019, 1:37pm UTC](https://discourse.processing.org/t/quicksort-visualization/14120/10 "2019-09-28T13:37:59Z")

</div>

Your welcome - enjoy