Реализовать Counting Sort в стиле C++

Стало интересно, как оформить алгоритм сортировки подсчетом из Кормена по стандартам C++ для сортировки произвольных объектов, а не только чисел. Достоинство этой сортировки, кроме скорости, в том, что она устойчива, то есть если набор каких-то объектов пронормирован целыми числами, но алгоритм не будет перемешивать объекты с одинаковой нормой. Можно либо задать функцию нормировки, либо создавать пары "объект - число", которые передаются в функцию сортировки. Вот код:
#include #include #include
//Сортировка подсчетом void csort(const std::vector in, std::vector &out, int max){ int *c = new int[max + 1]; std::memset(c, 0, (max + 1) * sizeof(int)); out.resize(in.size()); for(int i = 0; i < in.size(); i++) c[in.at(i)]++; for(int i = 1; i < max + 1; i++) c[i] = c[i] + c[i - 1]; for(int i = in.size() - 1; i >= 0; i--){ c[in[i]]--; out[c[in[i]]] = in[i]; } delete[] c; }
int main(){ std::vector u, v; int a[17] = {0, 4, 7, 1, 2, 3, 3, 3, 9, 11, 13, 15, 15, 2, 17, 16, 16}; size_t max = 17;
u.assign(a, a + 17); std::copy(u.begin(), u.end(), std::ostream_iterator(std::cout, " ")); csort(u, v, max); std::cout << std::endl; std::copy(v.begin(), v.end(), std::ostream_iterator(std::cout, " ")); std::cin >> max; }
В C++ советуют вместо массивов везде использовать векторы. Можно каким-то образом в строке int *c = new int[max + 1]; использовать вектор? И надо ли это вообще? В первой части c[in.at(i)]++; я использую функцию at() вместо прямого обращения по индексу in[i], а в конце обращаюсь к элементам напрямую. Какой способ лучше? Например, что в последнем цикле множество функций at() будет очень затруднять чтение кода.
Как еще можно переписать этот код? Как правильно писать абстракцию типа данных, которые не являются числами и которые надо сортировать?

Ответ

В C++ советуют вместо массивов везде использовать векторы. Можно каким-то образом в строке int *c = new int[max + 1]; использовать вектор?
Да, примерно так:
std::vector c(max + 1, 0);
Оно же будет и инициализацией нулями.
И надо ли это вообще?
Это Ваша гарантия того, что в случае exception ниже, выделенная память будет освобождена. Т.е. в общем случае да, надо.
В первой части c[in.at(i)]++; я использую функцию at() вместо прямого обращения по индексу in[i], а в конце обращаюсь к элементам напрямую. Какой способ лучше? Например, что в последнем цикле множество функций at() будет очень затруднять чтение кода.
at - генерирует out_of_range exception, в случае, если Вы пытаетесь обратиться к элементу вне размеров массива. Обращение "напрямую" в этом случае приведет к undefined behavior. В остальном они идентичны. На мой взгляд, т.к. Вы точно знаете размеры своего массива и никак не рискуете обратиться вне, и никто, кроме Вас и этого потока этот массив не изменяет, Вы смело можете обращаться "напрямую".
Как еще можно переписать этот код?
Красивый пример предложен в соседнем ответе :)
Я же предложу обратить внимание на возможные проблемы кода.
1) int i = in.size() - 1 - размер массива имеет тип size_t, который с хорошим шансом больше, чем int. И самая печаль, если он имеет ту же разрядность, но, например, unsigned. Это может при определенном размере массива дать Вам отрицательное стартовое значение. И в случае обращения по at(), Вы получите exception, и просто потечете памятью там, где делаете new int, а в случае обращения напрямую, будет undefined behavior, и Ваш процесс, например, полезет взламывать Пентагон :)
2) c[i] = c[i] + c[i - 1]; - теоретически это может привести к переполнению, и получению веселья. Но метод подсчета не используется при большом разбросе значений, а минимум у Вас не устанавливается и по дефолту 0, поэтому на это можно (из соображений здравого смысла) не обращать внимания.
3) Эту часть я бы заменил на более простое.
out.resize(in.size()); //... for(int i = 1; i < max + 1; i++) c[i] = c[i] + c[i - 1]; for(int i = in.size() - 1; i >= 0; i--){ c[in[i]]--; out[c[in[i]]] = in[i];
Вот на это:
out.reserve(in.size()); for(size_t i = 0; i < max + 1; i++) for (size_t j = c[i]; j > 0; --j) out.push_back(i);
Имхо так понятнее, что происходит.
Как правильно писать абстракцию типа данных, которые не являются числами и которые надо сортировать?
Зависит от того, по какому признаку их надо сортировать. Исходя из этого и будет необходимо сформировать целочисленное представление этого признака. Если же признаков для сортировки нет, и надо отсортировать "как-нибудь", лучше всего сразу на месте объявить массив отсортированным. Ну, по какому-то существующему, известному только Вам секретному правилу :)