Comparison counting sort

main.cpp

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

using namespace std;


template<typename T>
vector<T> comparison_counting_sort(vector<T> &array, function<bool(T, T)> key_func) {
    vector<int> frequencies(array.size(), 0);
    vector<T> result(array.size());

    for (int i = 0; i < array.size() - 1; ++i) {
        for (int j = i + 1; j < array.size(); ++j) {
            if (key_func(array[i], array[j]))
                frequencies[j] += 1;
            else
                frequencies[i] += 1;
        }
    }

    for (int i = 0; i < array.size(); ++i)
        result[frequencies[i]] = array[i];

    return result;
}

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

int main() {
    std::function<bool(int, int)> comp = std::less<int>();

    vector<int> array{3, 5, 3, 7, 7, 1, 4};
    vector<int> result = comparison_counting_sort(array, comp);
    

    cout << "Array:" << endl;
    print_vector(array); // 3 5 3 7 7 1 4

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