Quick Sort in C++ with O(n log n) Time Complexity

In this video lesson we will study how the Quick Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Quick Sort:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Your algorithm should run in O(n log n) time and use O(log n) extra space.

Understanding the Problem

The core challenge of the Quick Sort problem is to sort an array of integers in ascending order efficiently. Quick Sort is a widely used sorting algorithm due to its average-case time complexity of O(n log n) and its in-place sorting capabilities, which means it requires only a small, constant amount of additional storage space.

Quick Sort is significant in many applications, including database query optimizations, search algorithms, and more. However, it can be tricky to implement correctly due to the partitioning step, which is crucial for its performance.

Approach

To solve the Quick Sort problem, we can break down the approach into several steps:

1. Choose a Pivot: Select an element from the array to act as the pivot. Common strategies include picking the first element, the last element, or a random element.
2. Partition the Array: Rearrange the elements in the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it.
3. Recursively Apply Quick Sort: Apply the same process to the sub-arrays formed by partitioning.

A naive solution might involve repeatedly scanning the array to find the correct position for each element, but this would result in a time complexity of O(n^2). Instead, the partitioning step in Quick Sort ensures that each element is moved at most once, leading to an average-case time complexity of O(n log n).

Algorithm

Here is a step-by-step breakdown of the Quick Sort algorithm:

1. Base Case: If the array has one or zero elements, it is already sorted.
2. Partitioning: Choose a pivot and partition the array into two sub-arrays: one with elements less than the pivot and one with elements greater than the pivot.
3. Recursive Sorting: Recursively apply Quick Sort to the sub-arrays.

Code Implementation

Below is the C++ implementation of the Quick Sort algorithm:

#include <iostream>
#include <vector>

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(vector<int>& nums, int low, int high) {
    int pivot = nums[high]; // Choosing the last element as pivot
    int i = low - 1; // Index of smaller element

    for (int j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot
        if (nums[j] <= pivot) {
            i++; // Increment index of smaller element
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[high]);
    return i + 1;
}

// QuickSort function
void quickSort(vector<int>& nums, int low, int high) {
    if (low < high) {
        // Partitioning index
        int pi = partition(nums, low, high);

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

// Main function to test the QuickSort algorithm
int main() {
    vector<int> nums = {3, 1, 3, 2, 5, 4};
    quickSort(nums, 0, nums.size() - 1);

    // Print the sorted array
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

Complexity Analysis

The time complexity of Quick Sort is as follows:

• Best Case: O(n log n) - This occurs when the pivot divides the array into two nearly equal halves.
• Average Case: O(n log n) - This is the expected time complexity for a random pivot.
• Worst Case: O(n^2) - This occurs when the pivot is the smallest or largest element, leading to unbalanced partitions.

The space complexity of Quick Sort is O(log n) due to the recursive stack space used during the sorting process.

Edge Cases

Potential edge cases include:

• An empty array: The algorithm should handle this gracefully and return an empty array.
• An array with one element: The algorithm should recognize that it is already sorted.
• An array with all identical elements: The algorithm should still function correctly and return the same array.

Testing

To test the Quick Sort algorithm comprehensively, consider the following test cases:

• Simple cases: [3, 1, 3, 2, 5, 4]
• Edge cases: [], [1], [1, 1, 1, 1]
• Large arrays: Generate large arrays with random elements to test performance.

Testing frameworks such as Google Test can be used to automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching sorting problems like Quick Sort, consider the following tips:

• Understand the problem requirements and constraints.
• Break down the problem into smaller, manageable steps.
• Consider different pivot selection strategies to optimize performance.
• Practice implementing the algorithm to gain a deeper understanding.

Conclusion

Quick Sort is a powerful and efficient sorting algorithm with an average-case time complexity of O(n log n). Understanding its partitioning mechanism and recursive nature is crucial for implementing it correctly. By practicing and exploring different pivot selection strategies, you can optimize its performance for various scenarios.

Additional Resources

For further reading and practice problems related to Quick Sort, consider the following resources:

• Quicksort - Wikipedia
• Quick Sort - GeeksforGeeks
• Sorting Problems - LeetCode