Pseudocode of QuickSort with Its analysis

QuickSort algorithm uses the divide and conquers method to sort an Array. It contains a function that is used to partition (divide the array) using a pivot element. Generally, the pivot element selected is the rightmost element of the array (You can select the leftmost also but some conditions will change). The elements of the array are interchanged in such a way that the pivot element position is fixed and all the elements left to it are smaller and the right ones are larger than it.

Pseudocode of QuickSort

Here arr is the array, ‘l’ is the leftmost index of the array/subarray and ‘r’ is the rightmost array index. Here we assume that the array starts from index 0.

function quickSort(arr, l, r)
    if l < r
        pivotIndex = partition(arr, l, r)
        quickSort(arr, l, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, r)

function partition(arr, l, r)
    pivot = arr[r]
    i = l - 1
    
    for j = l to r - 1
        if arr[j] < pivot
            i = i + 1
            swap arr[i] and arr[j]
    
    swap arr[i + 1] and arr[r]
    return i + 1

Explanation of QuickSort Pseudocode

QuickSort is a divide-and-conquer algorithm. It divides a large array into two smaller sub-arrays: the low elements and the high elements. QuickSort can then recursively sort the sub-arrays.

The quickSort Function

Start by Checking the Condition: The function begins by ensuring that there are at least two elements to sort (if l < r). If l is not less than r, the array or sub-array has one or no element and does not need sorting.
Partitioning the Array: If there are elements to sort, it calls the partition function. This function is designed to pick an element as the pivot and partitions the array around the pivot, placing smaller elements to its left and larger elements to its right.
Recursive Sorting: After partitioning, the array is divided into two parts: before and after the pivot index. The quickSort function is then called recursively on these two parts (quickSort(arr, l, pivotIndex - 1) for the left sub-array and quickSort(arr, pivotIndex + 1, r) for the right sub-array), continuing the process of dividing and sorting until the entire array is sorted.

The partition Function

Pivot Selection: The last element of the array or sub-array (arr[r]) is chosen as the pivot.
Rearranging Elements: The goal here is to move elements that are smaller than the pivot to its left and those that are larger to its right. The index i is initially set to one position before the start of the sub-array (l - 1). This index will keep track of the “border” between smaller and larger elements compared to the pivot.
Looping through the Array: The loop (for j = l to r - 1) iterates through each element of the array/sub-array, comparing them with the pivot.
- If an element (arr[j]) is less than the pivot, the border (i) is moved one step forward (i = i + 1), and this element is swapped with the element at the border, effectively placing it in the correct position (before the pivot in the final array).
Placing the Pivot: After all elements have been compared with the pivot, the pivot itself is swapped with the element at the border’s next position (i + 1). This ensures the pivot ends up between the elements smaller and larger than itself.
Returning the Pivot Index: Finally, the function returns the index (i + 1) where the pivot is placed, so the quickSort function can use it to divide the array for further sorting.

Example of Quick Sort

arr = [10, 7, 8, 9, 1, 5]

We have to sort this array, so we’ll call quickSort(arr, 0, 5) because our array starts at index 0 (l=0) and ends at index 5 (r=5).

Initial Call: quickSort(arr, 0, 5)

Check if l < r: Yes, 0 < 5, so we proceed.
Call partition(arr, 0, 5): We’ll find a pivot index around which to divide the array.

First Call to Partition

Pivot: Choose arr[5] = 5 as the pivot.
Rearranging: Starting with i = -1. For each j from 0 to 4, if arr[j] < 5, we swap arr[i + 1] and arr[j], then increase i by 1.
- arr[0] = 10, not less than 5, no swap.
- arr[1] = 7, not less than 5, no swap.
- arr[2] = 8, not less than 5, no swap.
- arr[3] = 9, not less than 5, no swap.
- arr[4] = 1, less than 5, swap arr[i + 1] (which is arr[0]) with arr[4]. The array becomes [1, 7, 8, 9, 10, 5].
Final Swap: Swap arr[i + 1] with arr[r] (pivot), making the array [1, 5, 8, 9, 10, 7].
Pivot Index: Return i + 1 = 1.

The pivot value 5 is now correctly placed, with all elements smaller than 5 to its left, and all elements greater to its right.

Recursive Calls

The array is now divided into two parts, with the pivot index at 1:

Left of the pivot: quickSort(arr, 0, 0): This sub-array is already sorted because it has only one element.
Right of the pivot: quickSort(arr, 2, 5): We repeat the process for this sub-array.

Let’s focus on the second call quickSort(arr, 2, 5), assuming further partitioning and recursive calls eventually sort the array. For brevity, let’s skip to the array’s state after each part is sorted, leading to a final sorted array:

Final sorted array: [1, 5, 7, 8, 9, 10]

QuickSort Analysis

Partition function takes O(n) time to compute for an array of size n.

Worst-case

The worst-case occurs when the size of the array after each partition is decreased by 1 after each iteration. Such cases occur when the array is: sorted either in ascending or descending order & when all the elements are identical.

T(n)= T(n-1)+ O(n)

So, after back substitution

T(n) = O(n*n)

Best-case

The best-case occurs when the size of the array decreases either into half or into some constant ratio.

When the array breaks into n/2 sizes:

T(n)=2T(n/2) + O(n)

Applying Master’s theorem,

T(n)= Θ(n*log n)

There are Various optimizations that can be applied to QuickSort to improve its worst-case behavior. These optimizations include choosing a random pivot, using the “median-of-three” pivot selection strategy, or switching to an alternative sorting algorithm (such as HeapSort) for small subarrays.

Overall, the QuickSort algorithm is mostly used and efficient sorting algorithm.

Pseudocode of QuickSort with Its analysis