Quicksort

Quicksort is a sorting algorithm, used to place the elements of an array into an order. That order is based on comparison —  the things being sorted must have a “less than” / “greater than” relationship. (Source).

First, enjoy this adorably helpful animation (quicksort at 1:03 mark).

Of course there are many more efficient implementations of a quicksort method, but here’s mine at the moment:

As with my previous post on recursion, I find it helpful to break things out in a very visual way. Let’s step through it.

We start with our main input array, [5, 4, 3, 2, 1]. We select a pivot point at the midpoint (here that’s index 2, which has a value of 3.

We then separate each half of the original input array into two partitions (leftArr and rightArr).

quicksort1

We then loop through each value in the input array. If the value at the current index is less than the value at our pivot index, we push the value to an array holding “less than” values (here, that’s newLeftArr). If the value at the current index is greater than the value at our pivot index, the value is pushed to an array holding “greater than” values (newRightArr).

The value at the pivot index is skipped. It’s the comparison point for the partitions and doesn’t not need to be considered against itself.

At the end of all this, we make recursive calls to the two partitions we have created.

quicksort2

We recursively call quickSort on the partitions. Here, we enter the same comparison process on the input array [2, 1]:

quicksort3

This produces a new set of partitioned arrays, which we again evaluate with recursive calls to quickSort.

quicksort4

The two input arrays here, [ ] and [ 2 ], meet our base case, if(length <= 1){ return arr; }. There’s no further evaluation, and both return the input arrays [ ] and [ 2 ].

quicksort5

We walk through the same steps, moving through quickSort[ 5, 4 ] (queued up after our first partition). Again, we arrive at our base case, returning an empty and single-value array.

quicksort6

Now our results bubble up through the existing recursive calls.

quicksort7

And finally up to our first call:

quicksort8

Resolved and sorted, we return our sorted array, [ 1, 2, 3, 4, 5 ].

Leave a Reply

Your email address will not be published. Required fields are marked *