84 lines
1.9 KiB
C++
84 lines
1.9 KiB
C++
//
|
|
// Created by Vicente Ferrari Smith on 13.02.26.
|
|
//
|
|
|
|
#ifndef V_MISC_H
|
|
#define V_MISC_H
|
|
|
|
#include <vector>
|
|
|
|
std::vector<char> loadFile(const char* path);
|
|
|
|
|
|
template<typename T, typename F>
|
|
std::vector<T> counting_sort(const std::vector<T> &array, F f) {
|
|
int64_t n = array.size();
|
|
if (n == 0) return {};
|
|
std::vector<T> output(n);
|
|
|
|
int64_t max_val = 0;
|
|
int64_t min_val = 0;
|
|
|
|
for (const auto& it : array) {
|
|
const int64_t ssy = f(it);
|
|
if (ssy > max_val) max_val = ssy;
|
|
if (ssy < min_val) min_val = ssy;
|
|
}
|
|
|
|
const size_t range = max_val - min_val + 1;
|
|
std::vector<int64_t> count(range, 0);
|
|
|
|
for (const auto& it : array) {
|
|
count[f(it) - min_val] += 1;
|
|
}
|
|
|
|
for (int64_t i = 1; i < range; ++i) {
|
|
count[i] += count[i - 1];
|
|
}
|
|
|
|
for (int64_t i = n - 1; i >= 0; --i) {
|
|
const int64_t ssy = f(array[i]);
|
|
output[count[ssy - min_val] - 1] = array[i];
|
|
count[ssy - min_val] -= 1;
|
|
}
|
|
|
|
return output;
|
|
}
|
|
|
|
template <typename T, typename F>
|
|
std::vector<T> counting_sort_descending(const std::vector<T>& array, F f) {
|
|
int64_t n = array.size();
|
|
if (n == 0) return {};
|
|
std::vector<T> output(n);
|
|
|
|
int64_t max_val = 0;
|
|
int64_t min_val = 0;
|
|
|
|
for (const auto& it : array) {
|
|
const int64_t ssy = f(it);
|
|
if (ssy > max_val) max_val = ssy;
|
|
if (ssy < min_val) min_val = ssy;
|
|
}
|
|
|
|
const int64_t range = max_val - min_val + 1;
|
|
std::vector<int64_t> count(range, 0);
|
|
|
|
for (const auto& it : array) {
|
|
count[f(it) - min_val] += 1;
|
|
}
|
|
|
|
for (int64_t i = range - 2; i >= 0; --i) {
|
|
count[i] += count[i + 1];
|
|
}
|
|
|
|
for (int64_t i = n - 1; i >= 0; --i) {
|
|
const int64_t ssy = f(array[i]);
|
|
output[count[ssy - min_val] - 1] = array[i];
|
|
count[ssy - min_val] -= 1;
|
|
}
|
|
|
|
return output;
|
|
}
|
|
|
|
#endif //V_MISC_H
|