The Recursive QuickSort Implementation in C++

Quicksort is the de-factor sorting algorithm that is widely used. Its average runtime complexity is O(nlogn) and it’s usually implemented in either recursion or iterative style.

Quicksort can be easily implemented using Recursion. You can refer to the following posts:

• Javascript Coding Exercise: The QuickSort Implementation in Javascript
• How to Implement Quicksort Algorithm in Python – the Pythonic Way
• Greedy Algorithm to Find the Largest Perimeter Triangle by Sorting

C++ Quicksort implementation using vector

Likewise, the idea of quicksort is to choose a random pivot and separate the original list (vector) into three kinds: smaller ones, equal ones and the larger ones. Then recursively call the sorting function to sort the smaller and larger vector. Finally concate the three parts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        vector<int> lt;
        vector<int> eq;
        vector<int> gt;
        int p = nums[rand() % nums.size()];
        for (const auto &n: nums) { // separate the vector
            if (n < p) lt.push_back(n);
            else if (n == p) eq.push_back(n);
            else gt.push_back(n);
        }
        vector<int> lt1 = sortArray(lt); // recursively sort smaller group
        vector<int> gt1 = sortArray(gt); // recursively sort larger group
        lt1.insert(end(lt1), begin(eq), end(eq));
        lt1.insert(end(lt1), begin(gt1), end(gt1));
        return lt1;
    }
};

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        vector<int> lt;
        vector<int> eq;
        vector<int> gt;
        int p = nums[rand() % nums.size()];
        for (const auto &n: nums) { // separate the vector
            if (n < p) lt.push_back(n);
            else if (n == p) eq.push_back(n);
            else gt.push_back(n);
        }
        vector<int> lt1 = sortArray(lt); // recursively sort smaller group
        vector<int> gt1 = sortArray(gt); // recursively sort larger group
        lt1.insert(end(lt1), begin(eq), end(eq));
        lt1.insert(end(lt1), begin(gt1), end(gt1));
        return lt1;
    }
};

In the worst cases, the quicksort complexity will be O(n^2). For example, given a sorted array, and if every iteration, the smallest element in the list is picked as the pivot, then it requires sorting vector of size N, N-1, N-2 … 1, which has O(N^2) complexity.

–EOF (The Ultimate Computing & Technology Blog) —