C++ Coding Test Course, Quick Sort

Hello! In this session, we will take a closer look at the Quick Sort algorithm using C++. Quick Sort is a sorting algorithm that frequently appears in various programming interviews and algorithm exams. In this article, we will master Quick Sort through its concept, implementation, time complexity, and example problems.

1. Overview of Quick Sort

Quick Sort is a type of divide-and-conquer algorithm that efficiently sorts data. The algorithm works as follows:

1. Select a pivot element from the given array.
2. Divide the array into two sub-arrays based on the pivot.
   (Elements less than the pivot go to the left sub-array, while elements greater than the pivot go to the right sub-array.)
3. Recursively perform Quick Sort on both the left and right sub-arrays.
4. Once the sub-arrays are sorted, place the pivot in the middle to form the final sorted array.

1.1 Selecting a Pivot

There are several methods for selecting a pivot. Common methods include:

• Selecting the first element as the pivot
• Selecting the last element as the pivot
• Selecting a random element as the pivot
• Selecting the median as the pivot

It is important to choose an appropriate method as the pivot selection significantly impacts sorting performance.

1.2 Time Complexity of Quick Sort

The average time complexity of Quick Sort is O(n log n). However, in the worst-case scenario (e.g., when the array is already sorted), performance can degrade to O(n²). Good pivot selection methods are important to prevent this.

2. Problem Description

Now, let’s solve a problem using Quick Sort. Solve the following problem:

Problem: Given an array of integers, sort the array in ascending order using the Quick Sort algorithm.
Input: [10, 7, 8, 9, 1, 5]
Output: [1, 5, 7, 8, 9, 10]

3. Problem Solving Process

The steps to solve the problem are as follows:

3.1 Algorithm Implementation

First, let’s implement the Quick Sort algorithm in C++.

 
#include <iostream>
#include <vector>

using namespace std;

// Partition function
int partition(vector<int> &arr, int low, int high) {
    int pivot = arr[high]; // Select the last element as pivot
    int i = (low - 1); // Index for smaller elements

    for (int j = low; j < high; j++) {
        // If current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++; // Increment index of smaller elements
            swap(arr[i], arr[j]); // Swap elements
        }
    }
    swap(arr[i + 1], arr[high]); // Swap the pivot to the correct location
    return (i + 1); // Return the new index of the pivot
}

// Quick Sort function
void quickSort(vector<int> &arr, int low, int high) {
    if (low < high) {
        // Perform partition and get the pivot index
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1); // Sort the left sub-array
        quickSort(arr, pi + 1, high); // Sort the right sub-array
    }
}

// Main function
int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    quickSort(arr, 0, n - 1);

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

The code above implements the Quick Sort algorithm. The partition function divides the given array based on the pivot, and the quickSort function performs sorting recursively.

3.2 Code Explanation

Let’s take a step-by-step look at the code:

• partition function:
  • Selects the last element as the pivot.
  • Divides the given array based on the pivot.
  • Moves the pivot to its sorted position.
  • Returns the new pivot index.
• quickSort function:
  • Checks the base condition and makes recursive calls for sub-arrays.
  • Performs the process of “finding the pivot and sorting” for each sub-array.

3.3 Code Execution Result

When the code is executed, it produces the following output:

Sorted array: 1 5 7 8 9 10

We can confirm that the sorted array is printed correctly. This indicates that Quick Sort has been performed successfully.

4. Additional Considerations

There are several additional considerations when using Quick Sort:

4.1 Stability

Quick Sort is an unstable sorting algorithm. That is, the relative order of elements with the same value is not guaranteed after sorting. If stability is required, other sorting algorithms (e.g., Merge Sort) should be considered.

4.2 Memory Usage

Quick Sort operates recursively, using memory on the call stack. In the worst case, it can have O(n) space complexity, but on average, it is O(log n).

5. Quick Sort vs Other Sorting Algorithms

Compared to other sorting algorithms, Quick Sort has the following advantages and disadvantages:

5.1 Advantages

• Typically offers fast performance with an average of O(n log n).
• Requires less additional memory space.
• Supports recursive and intuitive implementations.

5.2 Disadvantages

• Can have O(n²) performance in the worst case.
• Is an unstable sort and the relative order of identical elements may change.

6. Conclusion

In this article, we implemented the Quick Sort algorithm using C++ and explored various aspects. Quick Sort is an efficient and widely used sorting algorithm, making it a common topic in algorithm exams or coding interviews. Understanding and implementing Quick Sort will greatly aid in coding tests.

Finally, try solving more problems using Quick Sort. Considering various cases will help deepen your understanding of this algorithm.