[Algo] 3-0. Sorting

前言：
在開始練習各種演算法題型時，最先需要養成的是，如何選用「適當」的演算法，題目往往不會只有一種解，但合適的演算法可以如同走捷徑一般，快速且優雅的達到目標。
在實作程式前，更重要的是，寫下一段 pseudo code，試著說明其複雜度，並觀察是否有冗餘的空間可以優化。
在腦海中模擬一遍程式碼之後，最後才是快速的將程式碼實作出來。
在這一章節，我們將練習如何將「想法」轉換成「實作」。並且我們必須熟悉如何計算其時間複雜度。

一、Cheat Table

首先我們需要先瞭解每一種資料結構的各種操作的時間複雜度，以便我們選擇適合的資料結構與演算法。
- 下面這種表的 Array, Stack, Queue, Linked List, Hash Table, Binary Search Tree 基本上是要背起來的，其餘的遇到再去認識就好。
接下來就輪到練習實作了，排序演算法是個很好的練習，試著把下表中的排序演算法完成，並且計算其時間複雜度吧。
- 參考題目 Leetcode 912. Sort an Array

二、Sorting Algorithm

0. 測資

這個 file 是我寫的測資，可以拿來測試自己的實作，用法是 #include "agtr.h"，之後用 judge() 函式測試你寫好的 function。

#include <iostream>
#include <random>
#include <vector>

using namespace std;

class agtr{
public:
    static vector<int> exec(int n, int minv, int maxv) {
        if (minv > maxv) return {};
        else if (minv == maxv) return vector<int>(n, minv);
        vector<int> res;
        random_device rd;
        mt19937 mt(rd());
        uniform_real_distribution<double> dist(minv, maxv);
        while (n--) {
            res.push_back(dist(mt));
        }
        return res;
    }
    static vector<int> exec(int n) {
        return exec(n, 0, 10);
    }

    static vector<int> exec() {
        return exec(10);
    }
    static void print(vector<int>& nums) {
        cout << "[";
        for_each(nums.begin(), nums.end()-1, [](int x) { cout << x << ","; });
        cout << *(nums.end()-1) << "]";
    }
    static bool check(vector<int>& nums, vector<int> copy) {
        sort(copy.begin(), copy.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != copy[i]) return false;
        }
        return true;
    }
    static void judge(void (*func)(vector<int>&)) {
        int n = 10;
        bool test = true;
        int cnt = 0;
        while (n--) {
            auto nums = exec();
            auto copy = vector<int>(nums.begin(), nums.end());
            print(nums);
            (*func)(nums);
            cout << "->";
            print(nums);
            int result = check(nums, copy);
            cout << "(" << (result ? "Pass" : "Fail") << ")" << endl;
            if (result) cnt++;
            test &= result;
        }
        if (test) {
            cout << "Pass! (10/10)" << endl;
        } else {
            cout << "Fail! (" << cnt << "/10)" << endl;
        }
    }
};

以下為測試的方式

# include "agtr.h"
void sort(vector<int>& nums) {...}  // 你的實作

int main() {
    agtr::judge(sort);      // 用這個函式測試你的實作
    return 0;
}

1. Bubble Sort

void sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = n-1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j+1]) swap(nums[j], nums[j+1]);
        }
    }
}

2. Selection SOrt

void sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n-1; i++) {
        int p = i;
        for (int j = i+1; j < n; j++) {
            if (nums[j] < nums[p]) p = j;
        }
        swap(nums[p], nums[i]);
    }
}

3. Insertion Sort

void sort(vector<int>& nums){
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        int j = i-1;
        int curr = nums[i];
        for (; j >= 0; j--) {
            if (nums[j] <= curr) {
                break;
            }
            nums[j+1] = nums[j];
        }
        nums[j+1] = curr;
    }
}

4. Heap Sort

void heapify(vector<int>& nums, int i) {
    int left = 2*i+1;
    int right = 2*i+2;
    int p = i;
    int n = nums.size();
    if (left < n && nums[left] < nums[p]) p = left;
    if (right < n && nums[right] < nums[p]) p = right;
    if (p != i) {
        swap(nums[i], nums[p]);
        heapify(nums, p);
    }
}
void sort(vector<int>& nums) {
    vector<int> vec(nums.begin(), nums.end());
    int n = vec.size();
    int parent = (n-1)/2;
    for (int i = parent; i >= 0; i--) {
        heapify(vec, i);
    }

    for (int i = 0; i < n; i++) {
        nums[i] = vec[0];
        vec[0] = vec.back();
        vec.pop_back();
        heapify(vec, 0);
    }
}

5. Tree Sort

class TreeNode {
private:
    TreeNode* left, *right;
    int val;
    TreeNode* insert(TreeNode* root, int val) {
        if (!root) {
            root = new TreeNode(val);
            return root;
        }
        if (val < root->val) {
            root->left = insert(root->left, val);
        } else {
            root->right = insert(root->right, val);
        }
        return root;
    }
    void dfs(TreeNode* root, vector<int>& nums) {
        if (!root) return;
        dfs(root->left, nums);
        nums.push_back(root->val);
        dfs(root->right, nums);
    }
public:
    TreeNode() {}
    TreeNode(int val)
        : val(val) {}
    TreeNode(int val, TreeNode* left, TreeNode* right)
        : val(val), left(left), right(right) {}

    void insert(int val) {
        insert(this, val);
    }
    vector<int> getArray() {
        vector<int> nums;
        dfs(this, nums);
        return nums;
    }

};

void sort(vector<int>& nums) {
    TreeNode* root = new TreeNode(nums[0]);
    for (int i = 1; i < nums.size(); i++) {
        root->insert(nums[i]);
    }
    nums = root->getArray();
}

6. Merge Sort

void merge(vector<int>& nums, int left, int mid, int right) {
    int i = left, j = mid + 1;
    vector<int> tmp;
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j])
            tmp.push_back(nums[i++]);
        else
            tmp.push_back(nums[j++]);
    }
    while (i <= mid) tmp.push_back(nums[i++]);
    while (j <= right) tmp.push_back(nums[j++]);
    for (i = left; i <= right; i++) {
        nums[i] = tmp[i-left];
    }
}

void sort(vector<int>& nums, int left, int right) {
    if (right <= left) return;
    int mid = left + (right-left)/2;
    sort(nums, left, mid);
    sort(nums, mid+1, right);
    merge(nums, left, mid, right);
}

void sort(vector<int>& nums) {
    sort(nums, 0, nums.size()-1);
}

7. Quick Sort

nt partition(vector<int>& nums, int left, int right) {
    int pivot = left;
    int i = left;
    int j = right+1;
    while (true) {
        while (i < right && nums[++i] < nums[pivot]);
        while (j > left && nums[--j] > nums[pivot]);
        if (i >= j) break;
        swap(nums[i], nums[j]);
    }
    swap(nums[pivot], nums[j]);
    return j;
}

void sort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int pivot = partition(nums, left, right);
    sort(nums, left, pivot-1);
    sort(nums, pivot+1, right);
}

void sort(vector<int>& nums) {
    sort(nums, 0, nums.size()-1);
}

8. Tim Sort

#define MIN_MERGE 32

int minRunLength(int n) {
    int r = 0;
    while (n >= MIN_MERGE) {
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}

void insertionSort(vector<int>& nums, int left, int right) {
    int n = nums.size();
    for (int i = left+1; i <= right; i++) {
        int j = i-1;
        int curr = nums[i];
        for (; j >= left; j--) {
            if (nums[j] <= curr) {
                break;
            }
            nums[j+1] = nums[j];
        }
        nums[j+1] = curr;
    }
}

void merge(vector<int>& nums, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    vector<int> tmp;
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j])
            tmp.push_back(nums[i++]);
        else
            tmp.push_back(nums[j++]);
    }
    while (i <= mid)
        tmp.push_back(nums[i++]);
    while (j <= right)
        tmp.push_back(nums[j++]);
    for (i = left; i <= right; i++) {
        nums[i] = tmp[i-left];
    }
}

void sort(vector<int>& nums) {
    int minRun = minRunLength(MIN_MERGE);
    int n = nums.size();
    for (int i = 0; i < n; i += minRun) {
        int hi = min((i + MIN_MERGE - 1), n-1);
        insertionSort(nums, i, hi);
    }
    for (int size = minRun; size < n; size <<= 1) {
        for (int left = 0; left < n; left += (size << 1)) {
            int mid = left + size - 1;
            int right = min((left + (size << 1) - 1), n-1);
            if (mid < right) {
                merge(nums, left, mid, right);
            }
        }
    }
}

9. Shell Sort

void sort(vector<int>& nums) {
    int n = nums.size();
    for (int gap = n>>1; gap > 0; gap>>=1) {
        for (int i = gap; i < n; i++) {
            int tmp = nums[i];
            int j;
            for (j = i; j >= gap && nums[j-gap] > tmp; j -= gap) {
                nums[j] = nums[j-gap];
            }
            nums[j] = tmp;
        }
    }
}

10. Counting Sort

void sort(vector<int>& nums) {
    vector<int> dp(10, 0);
    for (const auto& x : nums) {
        dp[x]++;
    }
    int j = 0;
    for (int i = 0; i < 10; i++) {
        while (dp[i]-- > 0) {
            nums[j++] = i;
        }
    }
}

接著閱讀：[Algo] 3-1. Two Pointer/Sliding Window

一、Cheat Table#

二、Sorting Algorithm#

0. 測資#

1. Bubble Sort#

2. Selection SOrt#

3. Insertion Sort#

4. Heap Sort#

5. Tree Sort#

6. Merge Sort#

7. Quick Sort#

8. Tim Sort#

9. Shell Sort#

10. Counting Sort#

一、Cheat Table

二、Sorting Algorithm

0. 測資

1. Bubble Sort

2. Selection SOrt

3. Insertion Sort

4. Heap Sort

5. Tree Sort

6. Merge Sort

7. Quick Sort

8. Tim Sort

9. Shell Sort

10. Counting Sort