3-Way Qucik Sort

In my last blog, a clean version of quick sort was introduced.

Time Complexity of Quick Sort

Quick sort’s average time complexity is $O(nlogn)$, worst time complexity is $O(n^2)$.

Average case: A list of random numbers. After each partition the array was splited into two subarrays which have similar lengths. Each partition costs $O(n)$ and we only need $logn$ such partitions. So the time complexity is $O(nlogn)$.

Worst case 1: A sorted list. Each partition can split the list into two subarrays: whose lengths varys a lot(e.g. len_part1 = 1, len_part2 = n - 2). So we need nearly n such partitions. So the time complexity is $O(n^2)$.

Under the worst cases, the quick sort algorithm become not that quick. One solution is choosing a pivot randomly instead of always choosing the first or last element as pivot.

Worst case 2: A list which contains many duplicates. My clean version of quick sort will move all nums which is smaller than pivot to its left and all nums which is larger than pivot to its right part. There is an example for illustration.

1
2
3
4
5
6
7

      *
arr: [3, 3, 2, 3, 3, 1, 4, 3]
After 1 partition:
                     *
par: [1, 3, 2, 3, 3, 3, 4, 3]
*: pivot's position

In this example, there are many 3s. So that each partition will not always generate two similar lengths subarrays. Which may also causes trouble like worst case 1.

This blog will introduce a 3-way partition to solve improve worst case 2. The main idea is to split array into 3 parts: left part consists of nums < pivot, middle part consists of nums == pivot and right part consists of nums > pivot.

Dutch National Flag Problem

The 3-way partition is actually the same problem with Dutch National Flag Problem, This problem can be described as: given n intergers which are all in 0, 1, or 2. Sort them so that all 0s occur firstly, 1s occur secondly, and 2s occur lastly.

Note: If you want to practice, Leetcode link is here. An simpler version of this problem is Move Zeros, which contains only 2 colors.

1
2
3
4

arr:
[1, 0, 0, 1, 1, 2, 0, 2]
After sort:
[0, 0, 0, 1, 1, 1, 2, 2]

If we move all 0s ahead, all 2s behind, then all 1s will automatically at mid. So the problem is solved.
Suppose we have two pointers: low and high, low points to current position that we can safely place a 0, high points to current position that we can safely place an 2. For each num, if it’s 0, we swap it with arr[low]; if it is 2, we swap it with arr[high]; if it is 1, nothing to do, we just move to the next num.

Below is the c++ code for this Dutch National Flag problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// Dutch National Flag Problem
void sortColors(vector<int>& nums) {
    int ln = nums.size();
    int low = 0, high = ln - 1, mid = 0;
    // low: put next 0, high: put next 2
    // we don't need to handle 1
    while (mid <= high) {
        if (nums[mid] == 0) {
            if (mid != low) {
                swap(nums[mid], nums[low]);
            } else {
                mid++;
            }
            low++;
        } else if (nums[mid] == 2) {
            if (mid != high) {
                swap(nums[mid], nums[high]);
            } else {
                mid++;
            }
            high--;
        } else {
            mid++;
        }
    }
}

3-Way Quick Sort

Similar to Dutch National Flag problem, the 3-way partition takes nums < piovt as 0s, nums > pivot as 2s, and nums == pivot as 1s. Below is the quick sort using 3-way partition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// 3-Way Quick Sort
void output(const vector<int>& vec) {
    for (auto x : vec) {
        cout << x << " ";
    }
    cout << "\n";
}
void quick_sort(vector<int>& arr, int s, int e) {
    if (s >= e) return;
    int low = s, high = e - 1, mid = s;
    int pivot = arr[s];
    while (mid <= high) {
        if (arr[mid] < pivot) {
            if (mid != low) {
                swap(arr[mid], arr[low]);
            } else {
                mid++;
            }
            low++;
        } else if (arr[mid] > pivot) {
            if (mid != high) {
                swap(arr[mid], arr[high]);
            } else {
                mid++;
            }
            high--;
        } else {
            mid++;
        }
    }
    quick_sort(arr, s, low);
    quick_sort(arr, high + 1, e);
    return;
}
int main(){
    vector<int> arr = {3, 5, 5, 5, 5, 0, 6,5};
    output(arr);
    quick_sort(arr, 0, arr.size());
    output(arr);
    return 0;
}