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.

Quescol 1-Minute Read

Quick Sort is a divide and conquer sorting algorithm that works by selecting a pivot element and dividing the array into two parts — elements smaller than the pivot go to the left, and larger elements go to the right. The same process is repeated (recursively) on both sides until the array becomes fully sorted. It works in-place and is one of the fastest sorting algorithms in practice, though its performance depends on choosing a good pivot. Quick Sort is not stable, but it’s highly efficient for large datasets and widely used in libraries like C++ STL.

QuickSort important Points:

• Algorithm Type: Divide and Conquer method.
• Main Idea: Select a pivot, partition the array, and sort subarrays recursively.
• Pivot Role: Divides the array into smaller (left) and larger (right) elements.
• In-Place Sorting: Uses very little extra memory (O(log n) stack space).
• Stability: Not stable — equal elements may change position.
• Efficiency: Very fast for average and random inputs.
• Performance Dependence: Speed depends on the pivot selection.
• Best Case Time Complexity: O(n log n)
• Average Case Time Complexity: O(n log n)
• Worst Case Time Complexity: O(n²) (when pivot selection is poor).
• Space Complexity: O(log n) due to recursion.

Let’s Understand in Depth

What is Quick Sort?

Quick Sort is a fast and efficient divide and conquer algorithm used to arrange data in order. It works by selecting one element as a pivot and then partitioning the array so that all smaller elements go to the left of the pivot and all larger elements go to the right. After this, the pivot is in its correct position in the sorted array. The same steps are then repeated recursively for the left and right subarrays until the entire array is sorted.

Quick Sort is an in-place sorting algorithm, meaning it sorts the elements within the same array without using extra memory. The only additional space needed is for recursive calls, which is O(log n) on average. Because it uses less memory and runs quickly, Quick Sort is one of the most commonly used sorting algorithms, having an average time complexity of O(n log n) and a worst-case time complexity of O(n²).

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

1. 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.
2. 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.
3. 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

1. Pivot Selection: The last element of the array or sub-array (arr[r]) is chosen as the pivot.
2. 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.
3. 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).
4. 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.
5. 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)

1. Check if l < r: Yes, 0 < 5, so we proceed.
2. 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]

C++ Program

#include <iostream>
using namespace std;

// Function to swap two elements
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Choose the last element as pivot
    int i = low - 1;        // Pointer for smaller element

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {   // If current element is smaller than pivot
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]); // Place pivot in correct position
    return i + 1;
}

// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // Partition index

        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Main function
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output

Sorted array: 1 5 7 8 9 10

Explanation

In above C++ program, the Quick Sort algorithm is implemented to sort an array of integers in ascending order. The program begins with a swap() function that exchanges the values of two variables using reference parameters. The partition() function then plays a key role in the sorting process by selecting the last element as the pivot and rearranging the array so that all elements smaller than the pivot are placed to its left and all greater elements to its right. It returns the final position of the pivot.

The quickSort() function applies the divide and conquer technique, where it recursively calls itself to sort the two subarrays — one before the pivot and one after it — until all elements are in the correct order. In the main() function, an integer array {10, 7, 8, 9, 1, 5} is declared, and the quickSort() function is called with the first and last indices of the array. Finally, the program prints the sorted array as output:  1 5 7 8 9 10.

QuickSort Complexities 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.

Advantages of Quick Sort

1. Very Fast in Practice: Quick Sort is generally faster than other sorting algorithms like Merge Sort and Heap Sort for most inputs.
2. Divide and Conquer Approach: It uses the divide and conquer method, which makes it efficient for large datasets.
3. In-Place Sorting: It doesn’t need extra space like Merge Sort, as it sorts the array using only a small amount of additional memory.
4. Cache Friendly: Since it works with local sections of the array, it takes advantage of CPU caching and improves performance.
5. Efficient for Average Case: On average, Quick Sort has a time complexity of O(n log n), which is very good for sorting.
6. Tail Recursive Optimization: It can be optimized to reduce recursion depth and save memory space.

Disadvantages of Quick Sort

1. Worst Case Performance is Poor: In the worst case (like when the array is already sorted or nearly sorted), its time complexity becomes O(n²).
2. Not Stable: Quick Sort is not a stable algorithm, meaning it may change the relative order of equal elements.
3. Recursive Overhead: It uses recursion, which can lead to stack overflow for very large datasets if not implemented carefully.
4. Difficult to Predict Performance: The efficiency of Quick Sort depends on the choice of the pivot element; a bad pivot can slow it down.
5. Less Suitable for Small Datasets: For very small arrays, simpler algorithms like Insertion Sort may perform better.

FAQs Questions

Basic Level

1. What is Quick Sort?
Quick Sort is a divide and conquer sorting algorithm that works by selecting a pivot element, partitioning the array around the pivot, and recursively sorting the subarrays.

2. Who developed the Quick Sort algorithm and when?
It was developed by Tony Hoare in 1959.

3. What is the basic idea behind Quick Sort?
The main idea is to divide the array into two parts based on a pivot — elements smaller than the pivot go to the left, and elements greater go to the right — then conquer by recursively sorting both sides.

4. What are the main steps involved in Quick Sort?

• Choose a pivot element.
• Partition the array around the pivot.
• Recursively apply Quick Sort to the left and right subarrays.
• Combine results (implicitly as recursion ends).

5. What is a pivot in Quick Sort?
The pivot is the element chosen to divide the array into two halves — smaller and larger elements.

6. How does the partitioning process work in Quick Sort?
It rearranges the array so that all elements smaller than the pivot are placed before it, and all greater elements are placed after it.

7. Is Quick Sort a stable sorting algorithm? Why or why not?
No, Quick Sort is not stable because equal elements might change their relative positions during partitioning.

8. What are the best, average, and worst case time complexities of Quick Sort?

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n²)

9. What is the space complexity of Quick Sort?
The space complexity is O(log n) due to the recursive function calls (stack space).

10. Why is Quick Sort considered better than Merge Sort in some cases?
Because it is faster in practice, uses less memory, and works in-place, while Merge Sort needs extra space.

Intermediate Level

11. What happens when the array is already sorted in Quick Sort?
If the pivot is always chosen as the first or last element, the array becomes unbalanced, leading to the worst-case time complexity O(n²).

12. How can we avoid the worst-case performance of Quick Sort?
By choosing a random pivot or median-of-three (first, middle, and last element) as the pivot.

13. Which pivot selection strategies can be used in Quick Sort?

• First element
• Last element
• Random element
• Median-of-three method

14. How does Quick Sort differ from Merge Sort in terms of memory usage?
Quick Sort works in-place (no extra array needed), while Merge Sort needs O(n) extra space.

15. Is Quick Sort an in-place sorting algorithm? Explain.
Yes, because it sorts the elements within the original array without using significant additional memory.

16. Can Quick Sort be implemented iteratively instead of recursively?
Yes, by using a stack to manually handle the subarray indices.

17. Why is Quick Sort faster in practice even though it has the same average complexity as Merge Sort?
Because it has less overhead, better cache performance, and fewer data movements.

18. What are tail recursion and tail call optimization in Quick Sort?
Tail recursion means the recursive call is the last operation in a function; compilers can optimize it to save stack space.

19. How can you make Quick Sort stable?
By using extra memory or linked list representation, ensuring equal elements maintain their relative order.

20. What is the role of partition schemes in Quick Sort?
Partition schemes like Lomuto and Hoare define how the pivot is placed and how the array is divided during sorting.

Advanced Level

21. Explain Hoare’s and Lomuto’s partition schemes. Which is more efficient?

• Lomuto’s scheme: Uses the last element as pivot, simpler but less efficient.
• Hoare’s scheme: Uses two pointers moving inward, fewer swaps, and is more efficient.

22. How does Quick Sort perform on linked lists compared to arrays?
It’s not efficient on linked lists because random access is not possible; Merge Sort works better for linked lists.

23. How can you implement Quick Sort using random pivot selection?
Select a random index between low and high, swap it with the last element, and use it as the pivot to reduce worst-case chances.

24. What are the real-world applications of Quick Sort?
Quick Sort is used in databases, libraries (like C++ STL), file systems, and other areas requiring fast in-memory sorting.

25. Why is Quick Sort preferred in C++ STL’s sort() function?
Because it is fast, efficient, in-place, and optimized for most real-world data patterns.