Optimization: Simplicity vs Speed: Part 2 — Quicksort vs Heapsort

Knowing when to simply or diversify code, when to use pre-built methods or create our own and what approach to take as a developer is crucial to efficiency.  Here at Beringer, our developers are dedicated to studying optimization for the utmost benefit of our clients. This blog examines the use of two sorting algorithms: Quicksort and Heapsort and how they relate to the runtime of an application.  Part of the application involved the sorting of an array of integers, accomplished through Quick and Heapsort.

The two algorithms operate rather differently but are considered rival implementations.  Runtime of sorting algorithms are defined in terms of “n,” where “n” is a variable representing the number of elements that need to be sorted.  The worst case, which computer scientists look at the most in academic research, of Quicksort is n² whereas Heapsort is n lg n (lg is a logarithm in base of 2 rather than the normal base 10).  A simple example of this would be if we had 8 elements to sort.  Quicksort, at its worst, would take 64 to sort it, whereas Heapsort would only take 24.  This is rather different in practice.  The average case shows that Quicksort runs at the same time as Heapsort though.  The reality is that in practice Quicksort actually runs quite a bit faster.  So let’s evaluate why.

The screenshot above should look familiar from  my Part 1 blog.  Here we are focusing on the runtime as it relates to sorting.  Notice Heapsort with Regex takes 1,713 milliseconds while the Quicksort only takes 485 milliseconds.  Quicksort is running an average of over three times faster than Heapsort.  A glance back at Part 1 will show the same results.  So what exactly is happening here?  It all comes down to the implementation.  Quicksort is referred to as a “divide and conquer” algorithm, one that separates the problem into several smaller problems before tackling it piece by piece.  Quicksort is faster because sequential elements in an array are likely to be stored near one another.  Because the problem is broken into smaller pieces, Quicksort moves around less and cuts down on significant runtime.  By contrast, Heapsort leaps all around the problem picking up the pieces whenever it finds one.

The issue is different from the Regex and Char-Ops comparison.  Quicksort is faster most of the time and for many applications.  This is why Microsoft built C# with Quicksort as its default sorting algorithm.  Heapsort does have its place though.  If there are a sufficient number of elements, Quicksort will eventually fall off in speed while Heapsort will guarantee its runtime.  Heapsort may be whacky, but you can always count on it to do as it promises.  When a program requires a massive amount of data be sorted securely and efficiently, developers may find Heapsort to be the better answer.  Just as with Regex and Char-Ops, developers must consider what code is appropriate to use and when.

Beringer Associates continues to evaluate its code to better optimize software for the needs of our clients. Please contact us to find out how we can support your business.