Is there a better way to implement count sort?-CodePudding

The following code implements count sort: an algorithm that sorts in O(n) time complexity, but with a (possibly) heavy memory cost. Is there any better way to go about this?

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> arr = { 12,31,300,13,21,3,46,54,44,44,9,-1,0,-1,-1 };
    // find the minimum element in the list
    int min = arr.at(std::distance(arr.begin(), std::min_element(arr.begin(), arr.end())));
    // offset for negative values
    for (auto& elem : arr) {
        elem -= min;
    }
    // new max
    int max = arr.at(std::distance(arr.begin(), std::max_element(arr.begin(), arr.end())));
    std::vector<std::pair<int, int>> vec;
    vec.resize(max   1);
    for (const auto& number : arr) {
        // handle duplicates
        if (!vec.at(number).second) {
            vec[number] = std::make_pair(number   min, 0);
        }
        vec.at(number).second  ;
    }
    std::vector<int> sorted_vec;
    for (const auto& pair : vec) {
        if (pair.second) {
            for (int i = 0; i < pair.second; i  ) {
                sorted_vec.push_back(pair.first);
            }
        }
    }
    std::for_each(sorted_vec.begin(), sorted_vec.end(), [](const int& elem) { 
        std::cout << elem << " "; 
    });
    return 0;
}

CodePudding user response：

with input A[0:n], max_element=k, min_element=0, for the counting sort:

time complexity: O(n k)
space complexity: O(k)

You can NOT get O(n) time complexity, with O(1) space complexity.

If your k is very large, you should not use count sort algorithm.

In your code, you use std::vector<std::pair<int, int>> to store the count. It will get O(2*k) space complexity. You can just use a array of int.

Like this way:

#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> arr = { 12,31,300,13,21,3,46,54,44,44,9,-1,0,-1,-1 };
    // find the minimum element in the list
    int min = *std::min_element(arr.begin(), arr.end());
    // offset for negative values
    for (auto& elem : arr) {
        elem -= min;
    }
    // new max
    int max = *std::max_element(arr.begin(), arr.end());
    std::vector<int> vec(max   1, 0);
    for (const auto& number : arr) {
        vec[number]  = 1;
    }
    std::vector<int> sorted_vec;
    for (int num = 0; num < vec.size(); num  ) {
        int count = vec[num];
        for (int i = 0; i < count; i  ) {
            sorted_vec.push_back(num   min);
        }
    }
    std::for_each(sorted_vec.begin(), sorted_vec.end(), [](const int& elem) { 
        std::cout << elem << " "; 
    });
    return 0;
}