# Leetcode刷題學習筆記-- Counting Sort, Radix Sort
## Counting Sort
### Reference
ref1 : [Counting Sort from GeeksforGeeks](https://www.geeksforgeeks.org/counting-sort/)
ref2 : [Counting Sort from Leetcode](https://leetcode.com/explore/learn/card/sorting/695/non-comparison-based-sorts/4437/)

### Introduction
當需要排序的數列範圍不是很大的時候，可以使用counting sort。
+ non comparison-based algorithm
+ non In Place algorithm

### Procedure
1. 宣告一個vector來記錄所以數值可能出現的範圍。

vector<int> nums{5, 3, -1, 2, 4};
auto [mn, mx] = minmax_element(begin(nums), end(nums));
int range = *mx - *mn + 1, shift = *mn;
vector<int> count(range);

2. 統計每個數字出現的次數

for(auto& n : nums)
    count[n - shift]++;

3. 計算prefix sum得到每個數字要排序的位置。

for(int i = 1; i < count.size(); ++i)
    count[i] += count[i - 1];

或是使用

partial_sum(count.begin(), count.end(), count.begin());

4. 使用一個和nums一樣大的vector來記錄排序後的結果，從後面走訪來保持stable。

vector<int> result(nums.size());
for(int i = nums.size() - 1; i >= 0; --i) {
    result[count[nums[i] - shift] - 1] = nums[i];
    count[nums[i] - shift]--;
}

5. 把結果回傳回去，或是覆蓋原本的輸入vector。

nums = result; // 會呼叫vector的copy assignment。

### Example
#### [75. Sort Colors](https://leetcode.com/problems/sort-colors/)

void sortColors(vector<int>& nums) {
    vector<int> count(3), tmp(nums.size());
    for(auto& n : nums) count[n]++;
    partial_sum(count.begin(), count.end(), count.begin());
    for(int i = nums.size() - 1; i >= 0; --i) {
        tmp[count[nums[i]] - 1] = nums[i];
        count[nums[i]]--;
    }
    nums = tmp;
}

#### [1200. Minimum Absolute Difference](https://leetcode.com/problems/minimum-absolute-difference/)

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    const auto [mn, mx] = minmax_element(begin(arr), end(arr));
    int range = *mx - *mn + 1, shift = *mn;
    vector<int> count(range);
    for(auto& n : arr) count[n - shift]++;
    int left = 0, right = left + 1, mindiff = INT_MAX;
    vector<vector<int>> ans;
    while(right < count.size()) {
        right = left + 1;
        while(right < count.size() && count[right] == 0) ++right;
        if(right < count.size()) {
            int diff = right - left;
            if(diff < mindiff) {
                mindiff = diff;
                ans = {{left + shift, right + shift}};
            } else if(diff == mindiff)
                ans.push_back({left + shift, right + shift});
            left = right;
        } else
            break;
    }
    return ans;
}

## Radix Sort
### Reference
ref : [Radix Sort from GeeksforGeeks](https://www.geeksforgeeks.org/radix-sort/)
ref : [Radix Sort from Leetcode](https://leetcode.com/explore/learn/card/sorting/695/non-comparison-based-sorts/4438/)
### Introduction
+ 所有的comparsion based sorting algorithm 最快就是$O(NlogN)$
+ 可以達到線性的time complxity只有counting sort和radix sort。
+ 但是counting sort對數字範圍很大的比較不利。
+ 從least significant digit一直排序到most significant digit
+ non in-place algorithm
+ Stable Sort
### Procedure
1. 先取得最大值或是最長的字串，因為這是要做多少次counting sort的基礎。
如果使用max_element得到的為iterator，必須在使用前先取值，不然數值會被第一次排序後改變。

vector<int> nums;
int maxv = *max_element(begin(nums), end(nums));

2. 對每個位數做counting sort
exp = 1, 10, 100, 1000, ...

for(int exp = 1; maxv / exp > 0; exp *= 10) {
    countSort(nums, exp);
}

3. 對某個位數進行counting sort

void countSort(vector<int>& nums, int exp) {
    vector<int> output(nums.size());
    vector<int> count(10); // 因為數字為0~9
    
    for(auto& n : nums) // 統計每個數字的個數
        count[(n / exp) % 10]++;
    
    // 計算每個數字的開頭index
    partial_sum(begin(count), end(count), begin(count));
    
    // 產生根據這個exp的排序
    for(int i = nums.size() - 1; i >= 0; --i) {
        output[count[(nums[i] / exp) % 10] - 1] = nums[i];
        count[(nums[i] / exp) % 10]--;
    }
    
    // 取代原先的input vector
    nums = output;
}

### Complexity
#### Time Complexity
==$O(W(N+K))$==
其中$O(N+K)$ 為counting sort，
N: 要被排序vector的大小
K: size of counting vector

W: 最大數值的位數。$W = log10(MaxValue)$
#### Space complexity
和counting sort一樣
$O(N+K)$
### Problems
#### [2343. Query Kth Smallest Trimmed Number](https://leetcode.com/problems/query-kth-smallest-trimmed-number/)

class Solution {
    void countSort(vector<string>& nums, int pos, vector<int>& idx) {
        vector<int> oidx(idx.size());
        vector<int> count(10);
        
        for(auto& n : nums)
            count[n[pos] - '0']++;
        partial_sum(begin(count), end(count), begin(count));
        
        for(int i = nums.size() - 1; i >= 0; --i) {
            string str = nums[idx[i]];
            char c = str[pos];
            int j = c - '0';
            oidx[count[j] - 1] = idx[i];
            count[j]--;
        }
        idx = oidx;
    }
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {        
        unordered_map<int, vector<int>> m;
        vector<int> idx(nums.size());
        iota(idx.begin(), idx.end(), 0);
        int sz = nums[0].size();
        for(int i = 1; i <= sz; ++i) {
            countSort(nums, sz - i, idx);
            m[i] = idx;
        }

        vector<int> rtn;
        for(auto& q : queries)
            rtn.push_back(m[q[1]][q[0] - 1]);
        
        return rtn;
    }
};

#### [164. Maximum Gap](https://leetcode.com/problems/maximum-gap/)

class Solution {
    void countSort(vector<int>& nums, int exp) {
        vector<int> output(nums.size());
        vector<int> count(10);
        for(auto& n : nums) count[(n / exp) % 10]++;
        partial_sum(count.begin(), count.end(), count.begin());
        for(int i = nums.size() - 1; i >= 0; --i) {
            int n = (nums[i] / exp) % 10;
            output[count[n] - 1] = nums[i];
            count[n]--;
        }
        for(int i = 0; i < nums.size(); ++i)
            nums[i] = output[i];
    }
public:
    int maximumGap(vector<int>& nums) {
        int maxval = *max_element(nums.begin(), nums.end());
        for(int exp = 1; maxval / exp > 0; exp *= 10)
            countSort(nums, exp);
        int ans = 0;
        for(int i = 1; i < nums.size(); ++i)
            ans = max(ans, nums[i] - nums[i - 1]);
        return ans;
    }
};

###### tags: `leetcode` `刷題`