Quick Sort in C++

Introduction

As the name suggests, a quick sort algorithm is known to sort an array of elements much faster (twice or thrice times) than various sorting algorithms.

Quick sort uses the divide and conquer technique where we partition the array around an element known as the pivot element, which is chosen randomly from the array. We solve the partitions to achieve an ordered array. Due to this reason, it is also known as the Partition Exchange Algorithm.

Working Of Quick Sort Algorithm In C++

The quick sort algorithm works in a Divide and Conquer fashion :

• Divide :-

Choose a pivot element first from the array. After that, divide the array into two subarrays, with each element in the left sub-array being less than or equal to the pivot element and each element in the right sub-array being greater. This will continue until only a single element is left in the sub-array.

• Conquer :

Recursively, sort the two subarrays formed with a quick sort.

• Merge :

Merge the already sorted array.

To discuss the working of the quick sort algorithm, let us take an example of an array:

1. Select the pivot element:-

Firstly, we choose a pivot element from the element. There are many different ways of choosing a pivot element : * Pick the first element as pivot always. * Pick the last element as pivot always. * Pick a random element as a pivot. * Pick median element as pivot.

In this article, we will consider the last element of the array as the pivot element.

2. Rearrange the array:-

We will rearrange the array such that elements smaller than the pivot element will come before the pivot element, and elements larger than the pivot element will come after the pivot element. Hence pivot element will come to its actual position.

In the above example, elements $[9,8]$ will come after $[7]$, and $[6,3,5,2]$ will come before $[7]$.

We rearrange the array in the following way :

• We initialize a pointer PIndex at index 0. This pointer will finally point to the pivot element's actual position.

• Then we traverse the array till Pivot with a pointer. Let us say i and check for the following condition :

This way, we put all the smaller elements to the left of PIndex and all the larger elements to the right of the PIndex.

• After array traversal and swapping, do PIndex= PIndex-1. This way, we rearranged the elements by partitioning the array into two subarrays- one to the left of the PIndex and one to the right of the PIndex.

3. Divide subarrays: We pass the pivot index's left and right subarray recursively to the same process followed above. Therefore, in the above example, we pass subarray - [0 to 3] with pivot element as $arr[3]$ and subarray - [5 to 6] with pivot element as $arr[6]$ as the argument to the quickSort function again.

Sorted Array:

Implementation Of Quicksort In C++

• Firstly, we initiate two pointers, lo and hi, to the leftmost and rightmost elements of the array.
• Then, we call the partition function, which rearranges the array such that all the smaller elements are left to the pivot element and all the larger elements are right to the pivot element.

It returns the final pivot index PIndex in the range [lo, hi].

• Recursively call the quicksort for the left subarray of Pindex and the right subarray of the Pindex.

Pseudo Code :

C++ Code :

Output :

Quick Sort Complexity

1. Time Complexity

• Best-case complexity :

Arises when the pivot element is the middle element or close to the middle element in a quick sort. When the pivot index is found in the middle, the recursion branch spreads more evenly; hence, $log(n)$ levels of the recursion tree are achieved.

Therefore, the best case time complexity is $O(n*log(n))$.

• Average Case Complexity :

It occurs when the array elements are not sorted at all. In other words, the array is fully unordered.

In this case, the average case scenario is similar to the best-case scenario as the jumbled array also gives an evenly divided recursion stack. Hence, Quicksort's average case time complexity is $O(n*log(n))$.

• Worst-Case Complexity :

In quick sort, worst-case complexity arises when the array is already sorted and the chosen pivot element is either the array's last or first element.

For example, if the array is $[1,2,3,4,5]$ and the pivot is chosen as the leftmost element, we always get the pivot index as the first element. If the pivot index is the first element of the sorted array, recursion stack branches in the $1: n-1$ ratio give rise to $n$ levels of the recursion tree.

Hence, Quicksort's worst-case time complexity is $O(n*n)$.

2. Space Complexity

As the algorithm is in place, where we sort the array in the original array, space complexity arises only because of the recursion stack. So, there must be a call stack entry for every one of these function calls.

This means that with an array of n integers, at worst, there will be n stack entries created, hence $O(n)$ worst-case space complexity.

The average case space complexity arises when we create $log(n)$ call stack entries. Hence average space complexity is $O(log n)$.

Characteristics Of Quick Sort

• A stable sorting algorithm :

Maintains the position of two equal elements relative to one another. Quick sort is not a stable algorithm because elements are swapped according to the pivot’s position (without considering their original positions).

• Quick sort algorithm is an in-place algorithm, which means array elements are sorted in the original array. In other words, the array is modified in the original array itself.
• Quick sort is an algorithm for quickly and efficiently sorting an array or list. Because the algorithm is always in place, quick sort is used when the space is limited.

3-Way Quick sort (Dutch National flag)

In simple quick sort, we partition the array around the pivot element and recurse for the left and the right subarrays.

So, when array contains redundant elements with multiple occurrences like $arr []=[1,1,2,4,2,1,1,2,4,1,1,4,4,4]$ with chosen pivot as 1 then we will be setting only one occurrence of 1 to its actual position in one recursive call.

To avoid this complexity, we use the 3-way Quick Sort algorithm, which partitions the array arr[l..r] into 3 subarrays :

• arr[l...i] : Left subarray with elements less than the pivot element.
• arr[i+1...j-1] : Subarray with elements equal to the pivot element.
• arr[j...r] : Right subarray with elements greater than the pivot element.

Through this, we set the actual position of all the occurrences of 1 in a single pass. Thus 3-way quick sort can be used when we have more than one redundant element in the array.

Pseudo Code :

• partition(arr, left, right, i, j) :

• quicksort(arr, left, right) :

Randomized Quick Sort

Sometimes it happens when choosing the rightmost element in the sorted array as a pivot, resulting in a worst-case time complexity of $O(n*n)$.

In such cases, we use randomized quick sort algorithm, which is nothing but choosing a random pivot element from the array. Here we are probably choosing a pivot near the center of the array, and when this happens, the recursion branches spread more evenly, making it fast to sort the array elements in $log(n)$ time.

Pseudocode(Lomuto partitioning) :

Quick Sort vs. Merge Sort

Quick Sort Applications

Quick sort provides a fast and systematic approach to sorting any list of things. Following are some of the applications where quick sort is used in real-world applications :

• Commercial computing :

They are used in various government and private enterprises for sorting data such as accounts/profiles by name or any given ID, transactions by time or place, files by name or date of creation, and so on.

• Numerical computations :

To accomplish accuracy in all calculations, most effectively created algorithms use priority queues and, in turn, sorting algorithms like quick sort.

• Information search :

Sorting algorithms help improve information search, and quick sort in c++ is one of the fastest among all the sorting algorithms.

Advantages Of Quick sort

• The time complexity of sorting an array of n elements in the average case scenario is $O(n*log(n))$ because an evenly divided recursion stack creates $logn$ levels for $n$ iterations. Hence, Quick sort is a bit faster(twice or thrice times) than merge sort.
• Inplace algorithm : There is no need for additional storage.
• Internal : Data is sorted in the main memory as a temporary array on RAM and not in the secondary memory.

Disadvantages Of Quick sort

• Execution time varies depending on the elements of the array.
• When the array is already sorted, the worst-case scenario for quick sort occurs$(O(n*n))$.
• It is an unstable algorithm and hence, loses the relative ordering of the same elements in the array.