Distribution counting sort

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

vector<int> distribution_counting_sort(vector<int> &array) {
    int min_value = *min_element(array.begin(), array.end());
    int max_value = *max_element(array.begin(), array.end());

    vector<int> frequencies(max_value - min_value, 0);
    vector<int> result(array.size());

    for (int &x: array)
        frequencies[x - min_value] += 1;

    for (int i = 1; i <= (max_value - min_value); ++i)
        frequencies[i] += frequencies[i - 1];

    for (int j, i = (array.size() - 1); i >= 0; --i) {
        j = array[i] - min_value;
        result[frequencies[j] - 1] = array[i];
        frequencies[j] -= 1;
    }

    return result;
}

template<typename T>
void print_vector(vector<T> &array) {
    for (T &value: array)
        cout << value << " ";
    cout << endl;
}

int main() {
    vector<int> array{3, 5, 2, 7, 0, 1, 4};
  
    cout << "Distribution Counting Sort" << endl;
    {
        vector<int> result = distribution_counting_sort(array);
      
        cout << "Array:" << endl;
        print_vector(array); // 3 5 2 7 0 1 4

        cout << "Sorted array:" << endl;
        print_vector(result); // 0 1 2 3 4 5 7
    }

    return 0;
}