Implementing Tony Hoare quick sort in JavaScript and LISP

Tony Hoare back in days in 1978 has authored Communicating Sequential Processes that is nowadays used for multithreading in Clojure and GO programming languages. Tony’s other prominent idea is a quick sort algorithm that offers N*log n best-case time complexity. In other words, quick sort algorithm works much faster comparing to other implementations.

Let’s take a glance over this topic. Here is the most intuitive bubble sort algorithm with time complexity N². It iterates over collection in two-nested loops and compares a pair of two adjacent values as it is shown on the image.

Bubble sort explanation from an article on Wikipedia

After uncommenting third line in order to run it with long-list of input values it results to 10 982 milliseconds on my notebook (MacBook Air).

Comparing to insertion sort implementation. It takes one element at a time and looks for a place for it in a list:

Insertion sort takes one element at a time and looks for its place in a resulting list. An image is from a wikipedia article.

Insertion sorts runs in 9191 milliseconds. Slightly faster than bubble sort.

But how fast is a quick sort approach? Let’s have a look:

Runs in just 124 milliseconds! Very impressive.

How does it run so fast? Quick sort takes a random element from an input list and generates two subsequent lists:

• the one with elements smaller than the element;
• and the one with elements greater than the element.

Then it applies the same approach to those new lists generating four nested lists (two for smaller list, two for greater) until the whole collection gets eventually sorted in a tree of lists. While merging those lists from a tree bottom to top you eventually construct a sorted result.

quick sort algorithm tree

As you probably noticed quick sort uses lists a lot. So it makes sense to use a programming language that is specifically designed to work with that kind of data structure. Here how does it look in LISP (Clojure):

Just ten lines of code that is twice smaller comparing to JavaScript.

Wrap-up

Quick sort implementation is much faster 124 milliseconds comparing to 10 982 msec and 9 191 msec in other algorithms. Its implementation looks particularly concise in LISP as it uses lists a lot.

Level Up Coding

Thanks for being a part of our community! Before you go:

• 👏 Clap for the story and follow the author 👉
• 📰 View more content in the Level Up Coding publication
• 🔔 Follow us: Twitter | LinkedIn | Newsletter

🚀👉 Join the Level Up talent collective and find an amazing job