Selection Sort + Merge Sort + Quick Sort + Rainbow Sort + Stack Sort

sorting.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

template<typename T>
void printVector(vector<T> &vec) {
    cout << "[";
    const size_t sz = vec.size();
    for (size_t i = 0; i < sz; ++i) {
        cout << vec[i];
        if (i == sz - 1)
            cout << "]";
        else
            cout << ", ";
    }
    cout << endl;
}

template<typename  T>
void swap(vector<T> &vec, int i, int j) {
    T temp = vec[i];
    vec[i] = vec[j];
    vec[j] = temp;
}

/* Selection Sort: T[O(n^2)] S[O(1)] */
void selectionSort(vector<int> &arr) {
    // empty or only one element
    if (arr.size() <= 1)
        return;
    
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        // find the index of min value in unsorted part
        int min_index = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_index])
                min_index = j;
        }
        // move the min element to the back of sorted part
        swap(arr, i, min_index);
    }
}

/* Merge Sort: T[O(nlogn)] S[O(n)]
   Time Complexity: O(n + nlogn) = O(nlogn)
       Recursion: O(1 + 2 + 4 + 8 + ... + n/2) = O(n)
       Merge: O(logn) levels, O(n) each level, O(nlogn) in total

   Space Complexity: O(n)
       There is no way to avoid using a temporary container when merging
*/
void merge(vector<int> &arr, vector<int> &helper, int start, int mid, int end) {
    helper = arr;

    int index = start;
    int left = start, right = mid + 1;
    while (left <= mid && right <= end) {
        if (helper[left] < helper[right]) {
            arr[index++] = helper[left++];
        } else {
            arr[index++] = helper[right++];
        }
    }

    while (left <= mid) {
        arr[index++] = helper[left++];
    }
}

void mergeSort(vector<int> &arr, vector<int> &helper, int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;
    mergeSort(arr, helper, left, mid);
    mergeSort(arr, helper, mid + 1, right);
    merge(arr, helper, left, mid, right);
}

void mergeSort(vector<int> &arr) {
    if (arr.size() <= 1) {
        return;
    }

    vector<int> helper(arr.size());
    mergeSort(arr, helper, 0, arr.size() - 1);
}

/* Quick Sort 
   Time Complexity:
       Best case: reduce half each time (logn levels), O(n) each level for quick select -> O(nlogn)
       Worst case: same problem size each level (n levels), O(n) each level for quick select -> O(n^2)

   Space Complexity: O(1) each level
       Best case: O(1 * logn) = O(logn)
       Worst case: O(1 * n) = O(n)
*/
int partition(vector<int> &arr, int left, int right) {
    int pivot_index = left + rand() % (right - left + 1);
    int pivot = arr[pivot_index];
    swap(arr, pivot_index, right);

    int l = 0, r = right - 1;
    while (l <= r) {
        if (arr[l] <= pivot) {
            l++;
        } else if (arr[r] > pivot) {
            r--;
        } else {
            swap(arr, l++, r--);
        }
    }

    swap(arr, l, right);
    return l;
}

void quickSort(vector<int> &arr, int left, int right) {
    if (left >= right) {
        return;
    }

    int pivot_index = partition(arr, left, right);
    quickSort(arr, left, pivot_index - 1);
    quickSort(arr, pivot_index + 1, right);
}

void quickSort(vector<int> &arr) {
    if (arr.size() <= 1) {
        return;
    }

    quickSort(arr, 0, arr.size() - 1);
}

/* Rainbow Sort (n objects with k colors): T[O(nlogk)] S[O(k)]
 彩虹排序严格地满足左边是小于等于mid的颜色，右边是大于mid的颜色
 左边的颜色范围: [start, mid]，右边的颜色范围: [mid + 1, end]  均为闭区间
 colors[left] < midcolor 和 colors[right] >= midcolor 搭配也可以，此时midcolor向上取整为(color1+color2)/2 + 1
*/
void rainbowSort(vector<int> &colors, int start, int end, int color1, int color2)
{
    if (start >= end) return;
    if (color1 >= color2) return;
    
    int midcolor = (color1 + color2) / 2;
    int left = start, right = end;
    while (left <= right) {
        while (left <= right && colors[left] <= midcolor) {
            left++;
        }

        while (left <= right && colors[right] > midcolor) {
            right--;
        }

        if (left <= right) {
            int temp = colors[left];
            colors[left] = colors[right];
            colors[right] = temp;
            left++;
            right--;
        }
    }

    rainbowSort(colors, start, right, color1, midcolor);
    rainbowSort(colors, left, end, midcolor + 1, color2);
}

/* Sort Using Two Stacks: T[O(n^2)] S[O(n)] */
stack<int> stackSort(stack<int> &nums) {
    stack<int> sorted;
    while (!nums.empty()) {
        int num = nums.top();
        nums.pop();

        size_t count = 0;
        while (!sorted.empty() && sorted.top() < num) {
            nums.push(sorted.top());
            sorted.pop();
            count++;
        }

        sorted.push(num);

        for (size_t i = 0; i < count; ++i) {
            sorted.push(nums.top());
            nums.pop();
        }
    }
    return sorted;
}

void stackSort(vector<int> &arr) {
    if (arr.size() <= 1) {
        return;
    }

    stack<int> nums;
    for (const int elem : arr) {
        nums.push(elem);
    }

    stack<int> sorted = stackSort(nums);

    const size_t sz = arr.size();
    for (size_t i = 0; i < sz; ++i) {
        arr[i] = sorted.top();
        sorted.pop();
    }
}