Count Sort

Textbook

Description:

Example:

Note

Idea:

• Stable
• Space O(n)
• Time: O(n)

Code:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void countSort(vector<int> & nums){
    int max_val=0;
    int n=nums.size();
    for(int i=0; i<n; ++i){
        if(max_val<nums[i]) 
            max_val=nums[i];
    }
    vector<int> count(max_val+1);
    for(int i=0; i<n; ++i){
        count[nums[i]]++;
    }

    int sum_sofar=0;
    for(int i=0; i<max_val+1; ++i){
        sum_sofar += count[i];
        count[i] = sum_sofar;
    }

    vector<int> output(n, 0);
    for(int i=0; i<n; ++i){
        output[count[nums[i]]-1] = nums[i];
        count[nums[i]]--;
    }

    swap(nums, output);
}


int main(){
    vector<int> input={3,4,2,5,6,7,2,3,3,8,9,23,43,22,1,23};

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

    // countSort(input);

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

}