Quicksort Algorithm
“What is Quicksort?” This is another question you’ll face in almost every tech job interview. Quicksort is probably the most used sorting algorithm because it’s easy to implement on average, gives high efficiency for large-data applications, it can be optimized for different needs and it’s relatively flexible on it’s input data.
Quicksort is a logarithmic-time algorithm, in other words, it has a Big O notation of O(log n)-(more about Big O Notation)- and depending on the way you implement it, it can be up to 2x or even 3x faster than Merge Sort or Heap Sort. Do note that the O(log n) speed is a best-case/average time, in worst case scenarios it can be O(n2) depending on the implementation.
Let’s explore one implementation of Quicksort using JavaScript (ECMA6):
const quickSort = list => {
if (list.length < 2)
return list; const pivot = list[0];
const left = [];
const right = []; for (let i = 1, total = list.length; i < total; i++){
if (list[i] < pivot)
left.push(list[i]);
else
right.push(list[i]);
} return [
...quickSort(left),
pivot,
...quickSort(right)
];
};
Quicksort uses recursion, divide-and-conquer and comparison-sort. It works by partitioning an array into two sub-arrays and then recursively sorting those arrays independently. To make it clear, let’s put this in 3 main steps:
- Choose the pivot (reference value).
- Divide the rest of the array in two, placing everything smaller than the pivot on the left and greater than the pivot on the right.
- Recursively apply the previous steps to the sub-arrays if they have more than 1 element.
In the following chart you can see our example algorithm in action; pivots are green, left arrays are red, and right ones are blue.
Another great advantage of Quicksort is that it can be implemented using task parallelism, so, with some tweaking of the code it can be used to get a great performance boost in multi-core processing or even better, GPU processing for extreme performance.
Although JavaScript is a single-threaded language, if your application requires a lot of power, you can enable parallel high-performance GPU processing via WebCL or use NodeJS and a library called node-cuda, the latter allows you to use NVIDIA CUDA™ -although you need an NVIDIA CUDA-enabled GPU-, but with hundreds of compatible models, you probably can get some science out of your current gaming computer!
Don’t forget to follow Cesar’s Tech Insights to learn more about software development and technology. Feel free to share your thoughts, comments, requests and suggestions at the bottom.
Happy coding!
Bibliography
Algorithms (4th Edition). — Robert Sedgewick and Kevin Wayne
Computer science in JavaScript: Quicksort. — Nicholas C. Zakas
Why you should use WebGL. — Florian Boesch
Write massively-parallel GPU code for the browser with WebGL. — Florian Boesch
