# Quick, Heap, Bucket & Introsort

As a neat visual followup to this post, open this website and take a look at the pseudocode implementations and animations .

## Quick sort

One of the most performant and most popular algorithms for sorting, quick sort is a divide and conquer algorithm somewhat similar to merge sort.

The idea is to chose the pivot in the middle and mark two pointers at the start and the end of array. If the left pointer value is less than pivot value, move it to the right. The same goes for the right pointer.

First, let’s implement a swap function.

1 2 3 4 5 6 7 |
function swap(arr, l, r){ var temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } |

Nice and simple, swapping two elements of array.

Now, lets partition the array switching the first item that is bigger or equal than pivot from the left array, with the first item that is smaller or equal than pivot from the right array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function partition(arr, left, right) { var pivot = arr[Math.floor((right + left) / 2)], i = left, j = right; while (i <= j) { while (arr[i] < pivot) { i++; } while (arr[j] > pivot) { j--; } /**/ if(i<=j){ swap(arr, i, j); i++; j++; } } return i; } |

And now, the function we are going to call. It should take the array as a param, and let’s make the l & r params optional so the function is more usable.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function quickSort(arr, l, r) { var index; if (arr.length > 1) { left = typeof l != 'number' ? 0 : l; right = typeof r != 'number' ? arr.length - 1 : r; index = partition(items, l, r); if (l < index - 1) { quickSort(arr, l, index - 1); } if (index < r) { quickSort(arr, index, r); } } return arr; } var result = quickSort(sortIt); |

Quicksort is the default sorting algorithm for large arrays in V8. With worst case performance of O(n^{2}) and best O(n log n) it can solve most of the sorting problems fast and efficiently.

When you dont need a stable sort, and average case performance matters more than worst case performance, quicksort is the way.

## Heap sort

Another very optimized algorithm, heavily used as a default sorting algorithm in C++, takes advantage of an auxiliary heap sorted in a binary tree manner.

First, the all the items of the original list are copied one by one to create our binary tree. There are two main conditions here.

1. Every node must have two children( unless you run out of nodes meaning that the tree is not balanced)

2. Every node must be bigger than it’s children (or smaller if sorting min first)

ex: for a [1,5,3,6,2,4] array, the procedure will look like this

add one to our tree, then add 5 as it’s child

1 2 3 4 5 |
1 / 5 |

As this does not satisfy our conditions, swap their places.

1 2 3 4 5 |
5 / 1 |

Now add 3 as the other child. No need to swap now, as 3 is less than 5.

You see where i am going with this.

now add 6

1 2 3 4 5 6 7 |
5 / \ 1 3 / 6 |

As 1 is less than 6, swap them. then again, as 5 is less than 6, swap it too.

1 2 3 4 5 6 7 |
6 / \ 5 3 / 1 |

Continue the procedure until all of the tree looks like this.

1 2 3 4 5 6 7 |
6 / \ 5 4 / \ / 1 2 3 |

And voila! We got our sorted tree!

After the tree is sorted, we can simply take each item from the top of the tree, being the highest value, and put the last value to the top of the tree to replace it.

1 2 3 4 5 6 7 8 9 |
3 / \ 5 4 / \ / 1 2 sortedList = [6]; |

Now, reorder the tree to comply to our 2 conditions.

1 2 3 4 5 6 7 8 9 |
5 / \ 3 4 / \ / 1 2 sortedList = [6]; |

And our tree is sorted again! You see where i’m going with this. As our tree is always sorted in a manner that the largest value is on top, we are simply picking cherries here to get our sorted list.

The worst and average case perfomance here is O(n log n), with O(1) space complexity needed for our auxiliary array representing our tree. In my next post, i will cover binary tree manipulation and usage, so i will not cover the implementation of this algorithm here. I took the liberty of googling it for you, so take a look at mgechev’s implementation of the algorithm in Javascript.

When you dont need a stable sort, and your worst case performance is more important than your average case performance, as it is always O(n log n), and you are sure you wont run out of stack or heap space, this is the way to go.

## Bucket sort

Well, although bucket sort is technically a sorting algorithm we can boil it down to a few lines of text. The idea behind this is that first you define some “buckets” or some criteria by which you want to divide your list, and then sort the each bucket individually, whether further using bucketsort recursively, or some other sorting algorithm. This algorithm can come in handy when you want to sort some distinct data by grouping it first. A good way to go when you are sure that your input is approximately uniformly distributed.

## Introsort

Introsort is a hybrid sorting algorithm that provides both fast average performance and optimal worst case performance by starting with quicksort and switching to heapsort when recursion depth exceeds a level based on the logarithm of the number of elements. That way you get an algorithm that has fast average performance and optimal wort case performance.

The basic code would look something like this

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
function sort(arr){ var max = log(arr.length)*2; introsort(arr, max); } function introsort(arr, max){ if(arr.length <= 1){ return; }else if(max = 0){ heapsort(A) }else{ var pivot = partition(arr); introsort(arr.slice(0, p), max-1); introsort(arr.slice(p+1), max-1); } } |

Maximum depth can be tuned for performance.