# 0 - Sorting algorithms

因為 sort 太經典了，今天就來實作一下經典的排序演算法：

1. Quicksort

2. Merge Sort

3. Counting Sort

就用 Leetcode # 912 - Sort an Array 當作測試介面。

Quicksort

Merge Sort

先自己憑著對演算法的印象，實作了一版爛爛的 Merge Sort：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size()-1);   
        return nums;
    }

private:
    void mergeSort(vector<int>& nums, int start, int end) {
        if(start == end)
            return;

        int mid = start + (end-start)/2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, mid+1, end);
    }

    void merge(vector<int>& nums, int l_start, int l_end, int r_start, int r_end) {
        int l=l_start, r=r_start, cur = l_start;

        vector<int> ans = nums;
        while(l<=l_end && r<=r_end) {
            if(nums[l] <= nums[r]) 
                ans[cur++] = nums[l++];
            else 
                ans[cur++] = nums[r++];
        }

        while(l<=l_end)
            ans[cur++] = nums[l++];

        while(r<=r_end)
            ans[cur++] = nums[r++];

        nums = ans;
    }
};

上面這一版會在最後一個 case TLE，所以稍微來改進一下：

上一個實作有個很浪費時間的地方是在 merge 時，直接讓 ans = nums，還有讓 nums = ans，所以會不斷做整個 array copying，這邊只修改需要修改的地方，提升效率。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size()-1);   
        return nums;
    }

private:
    void mergeSort(vector<int>& nums, int start, int end) {
        if(start >= end)
            return;

        int mid = start + (end-start)/2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, mid+1, end);
    }

    void merge(vector<int>& nums, int l_start, int l_end, int r_start, int r_end) {
        int l=l_start, r=r_start, cur = 0;

        // Improved
        vector<int> ans(l_end-l_start+1+r_end-r_start+1);

        while(l<=l_end && r<=r_end) {
            if(nums[l] <= nums[r]) 
                ans[cur++] = nums[l++];
            else 
                ans[cur++] = nums[r++];
        }

        while(l<=l_end)
            ans[cur++] = nums[l++];

        while(r<=r_end)
            ans[cur++] = nums[r++];

        // Improved
        for(auto a: ans)
            nums[l_start++] = a;
    }
};

效率提升到：

Runtime: 108 ms, faster than 16.72% of C++ online submissions for Sort an Array. Memory Usage: 40.3 MB, less than 5.55% of C++ online submissions for Sort an Array.

再加上一個判斷條件優化一下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.size() < 2)
            return nums;

        mergeSort(nums, 0, nums.size()-1);   
        return nums;
    }

private:
    void mergeSort(vector<int>& nums, int start, int end) {
        if(start >= end)
            return;

        int mid = start + (end-start)/2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, mid+1, end);
    }

    void merge(vector<int>& nums, int l_start, int l_end, int r_start, int r_end) {
        int l=l_start, r=r_start, cur = 0;

        vector<int> ans(l_end-l_start+1+r_end-r_start+1);
        while(l<=l_end && r<=r_end) {
            if(nums[l] <= nums[r]) 
                ans[cur++] = nums[l++];
            else 
                ans[cur++] = nums[r++];
        }

        while(l<=l_end)
            ans[cur++] = nums[l++];

        while(r<=r_end)
            ans[cur++] = nums[r++];

        for(auto a: ans)
            nums[l_start++] = a;
    }
};

效率再度小小提升：

Runtime: 96 ms, faster than 19.47% of C++ online submissions for Sort an Array. Memory Usage: 40.4 MB, less than 5.55% of C++ online submissions for Sort an Array.

最後再把 code 寫得漂亮一點：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.size() < 2)
            return nums;

        mergeSort(nums, 0, nums.size()-1);   
        return nums;
    }

private:
    void mergeSort(vector<int>& nums, int start, int end) {
        if(start >= end)
            return;

        int mid = start + (end-start)/2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, mid+1, end);
    }

    void merge(vector<int>& nums, int l_start, int l_end, int r_start, int r_end) {
        int l=l_start, r=r_start, cur = 0;

        vector<int> ans(l_end-l_start+1+r_end-r_start+1);
        while(l<=l_end && r<=r_end) {
            ans[cur++] = nums[l] <= nums[r] ? nums[l++] : nums[r++];
        }

        while(l<=l_end)
            ans[cur++] = nums[l++];

        while(r<=r_end)
            ans[cur++] = nums[r++];

        for(auto a: ans)
            nums[l_start++] = a;
    }
};

Counting Sort

Counting sort 的概念滿直覺的，就是數每個數字出現幾次，然後再根據出現次數寫到答案中，因為 time complexity 是 O(N)，所以很有效率。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.size() < 2)
            return nums;

        vector<int> table(50000+50000+1);
        for(auto n: nums) table[n+50000]++;

        int idx = 0;
        for(int i=0; i<table.size(); i++) {
            if(table[i]--) {
                nums[idx++] = i-50000;
                i--;
            }
        }

        return nums;
    }
};

執行起來的速度如下：

Runtime: 52 ms, faster than 97.46% of C++ online submissions for Sort an Array. Memory Usage: 16.5 MB, less than 22.22% of C++ online submissions for Sort an Array.