Quick Sort Algorithm

Powering many of the advanced systems in the world, algorithms come in various formats and have multiple uses

Algorithms provide a quick way to process data, carry out a specific task or solve a particular problem. It is quite like a recipe, which gives you a consistent result at the end. While there are millions of variations of algorithms, the core concepts are limited to around 20-30 in the world of computer science. Here, we look at the Quick Sort algorithm to understand what it does and its practical applications.

What is Quick Sort algorithm?

Quick Sort algorithm is a type of sorting algorithm in computer science. Its origin can be traced back to 1959, when it was developed by Tony Hoare, a British computer scientist. The Quick Sort algorithm is based on the divide-and-conquer paradigm. It works by identifying a pivot element from the array.

In the next step, the array is partitioned as per the rules. Elements that are smaller than the pivot are moved to the left, whereas larger elements are moved to the right. The pivot retains its position. The same process can be applied recursively to the left and right sub-arrays.

As compared to Merge Sort, the Quick Sort is categorized as an in-place algorithm. One of the primary benefits is that it requires very little extra space. However, stability can be an issue since equal elements could change the relative order.

To get best results with Quick Sort algorithm, it is important to follow some guidelines. For example, you have to ensure that you choose a random pivot. You need to take the median-of-three – first, middle and last elements. In case there are small subarrays less than or equal to 10 – 20 elements, it will be better to switch to Insertion Sort.

Partition schemes

In Quick Sort, there are two primary partition methods.

Lomuto Partition – This is the simpler version and the most commonly taught. In this partition, the last element in an array is selected as the pivot. Other elements are then rearranged around it. A single pointer is used to scan the array. Elements smaller than the pivot are moved to the left side in a group. When this process ends, the pivot moves to its final, correct position. This effectively splits the array into two parts.

Hoare Partition – This is considered as a more efficient algorithm, the original scheme developed by Tony Hoare. This partition system used two pointers, which start moving towards each other from the opposite ends of the array.

As the pointers move, the elements in the array start getting rearranged based on which side they are from a chosen pivot. The two pointers eventually meet or cross in the middle. The Hoare Partition carries out fewer swaps on average in comparison to the Lomuto scheme. This is why it is usually considered faster and more efficient for sorting tasks.

Real world examples of Quick Sort algorithm

Given below are some of the real-world examples of Quick Sort algorithm.

• C++ STL std::sort() uses IntroSort (Quick Sort + Heap Sort hybrid)
• Java’s Arrays.sort() uses Dual-Pivot Quick Sort (very fast)
• Python’s sorted() and list.sort() use Tim Sort

Various optimizations are also possible. For example, randomized Quick Sort can be used to shuffle an array or pick a random pivot. Tail recursion elimination can be used to always recurse on smaller subarrays first to reduce stack depth to O(log n). One can use hybrid with Insertion Sort for tiny arrays, which are common in real libraries. A 3-way partitioning can be used for arrays that have many duplicates.