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

#cpp #алгоритм #шаблоны_с++

                    
Стало интересно, как оформить алгоритм сортировки подсчетом из Кормена по стандартам
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() будет очень затруднять чтение кода. 

Как еще можно переписать этот код? Как правильно писать абстракцию типа данных, которые
не являются числами и которые надо сортировать?
    

Ответы

Ответ 1

В 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);


Имхо так понятнее, что происходит.

Как правильно писать абстракцию типа данных, которые не являются числами и которые
надо сортировать?

Зависит от того, по какому признаку их надо сортировать. Исходя из этого и будет
необходимо сформировать целочисленное представление этого признака. Если же признаков
для сортировки нет, и надо отсортировать "как-нибудь", лучше всего сразу на месте объявить
массив отсортированным. Ну, по какому-то существующему, известному только Вам секретному
правилу :)


Ответ 2

Простая копирующая сортировка подсчетом может выглядеть так:

#include 
#include 
#include 

// Сортировка подсчетом требует функцию, возвращающую ключ сортировки.
// Identity-функция возвращает переданный ей аргумент без изменений.
// Мы будем использовать ее в качестве функции для ключа по-умолчанию.
const auto identity = [](auto x) { return x; };
using Identity = decltype(identity);

// Сортировка подсчетом использует последовательный доступ для элементов на входе,
// и произвольный доступ для элементов на выходе алгоритма.
template
void counting_sort(
    ForwardIterator first, ForwardIterator last, // входная последовательность
    RandomAccessIterator out, // результат
    Key key = identity) // функция, выдающая ключ элемента
{
    // Проверяем что последовательность не пустая.
    if (first == last)
        return;

    // Определяем минимальный и максимальные ключи элементов.
    auto compare = [&](const auto& lhs, const auto& rhs) { return key(lhs) < key(rhs); };
    auto minmax = std::minmax_element(first, last, compare);
    auto min_key = key(*minmax.first);
    auto max_key = key(*minmax.second);
    // Если ключи не отличаются, то последовательность уже отсортирована.
    if (min_key == max_key) {
        std::copy(first, last, out);
        return;
    }

    // Выделяем массив для подсчета элементов.
    // Тут можно оптимизировать потребление памяти, если использовать счетчики меньшие
    // чем size_t, если размер входной последовательности достаточно мал.
    std::vector count(max_key - min_key + 1);
    // Подсчитываем количество элементов с одинаковым ключом.
    std::for_each(first, last, [&](const auto& x) { ++count[key(x) - min_key]; });
    // Обнуляем первый счетчик и вычисляем частичные суммы.
    // Если после подсчета в count было {2,2,2,2},
    // то после partial_sum там будет   {0,2,4,6},
    // т.е. индексы, по которым должны лежать элементы с одинаковым ключом.
    count[0] = 0;
    std::partial_sum(count.begin(), count.end(), count.begin());
    // Копируем элементы в выходной массив, увеличивая индексы в "count".
    // Копирование можно заменить на перемещение.
    std::for_each(first, last, [&](auto& x) { out[count[key(x) - min_key]++] = x; });
    // Код "count[key(x) - min_key]" встречается два раза, и его можно вынести в
отдельную функцию, например
    // auto count_ref = [&](const auto& x) -> std::size_t& { return count[key(x)
- min_key]; };
}