third.md

Подсчётом

Сортировка подсчётом (англ. counting sort) — алгоритм сортировки целых чисел в диапазоне от 0 до некоторой константы k или сложных объектов, работающий за линейное время.

Суть: есть исходный массив А и вспомогательный массив C с индексами от 0 до k - 1 (длины k) - его мы вначале заполняем нулями. Дальше мы просто проходим по А и записываем в С[i] количество чисел равных i (Ну то есть если у нас в массиве две троечки, то в C[3] будет 2)

Для примера есть массив А[1, 4, 1, 2, 7, 5, 2], k для удобства считаем = 10 C меняется с [0, 0, 0, 0, 0, 0, 0, 0, 0] на [0, 2, 2, 0, 1, 1, 0, 1, 0, 0]

Ну и под конец просто проходимся по массиву C от i = 0 до k - 1 и записываем в А i-ю позицию C[i] раз Короче говоря, записываем индекс массива (который как бы число из массива А) столько раз, сколько у нас посчиталось на шаге с подсчётом Так как мы всё это делаем последовательно, оно не будет выходить криво

void CountSort(vector<int>& a) {
    vector<int> c(k);
    for (int number = 0; number < k - 1; number++) {
        c[number] = 0;
    }

    for (int i = 0; i < a.size(); i++) {
        c[a[i]]++;
    }
    
    int pos = 0;
    for (int number = 0; number < c.size(); number++) {
        for (int i = 0; i <= c[number] - 1; i++) {
            a[pos] = number;
            pos++;
        }
    }
}

Работает эта говнина линейно за Thetta(n + k), памяти O(k);

Radix

Суть: невероятно, но... сортировка по разрядам чиселок / строк от меньшего к большему (LSD) или от большего к меньшему (MSD)

int digit(int x,int i){while(i--)x/=10; return x%10;}

void RadixSort(vector<int>& a) {
    vector<int> c(k);
    vector<int> b(a.size());
    for (int i = 1; i < m; i++) {
        
        for (int j = 0; j < c.size(); j++) {
            c[j] = 0;
        }

        for (int j = 0; j < a.size(); j++) {
            int d = digit(a[j], i);
            c[d]++;
        }

        int count = 0;
        for (int j = 0; j < c.size(); j++) {
            int tmp = c[j];
            c[j] = count;
            count += tmp;
        }

        for (int j = 0; j < a.size(); j++) {
            int d = digit(a[j], i);
            b[c[d]] = a[j];
            c[d]++;
        }

        for (int j = 0; j < a.size(); j++) {
            a[j] = b[j];
        }
    }
}

Оценка LSD Для чисел: пусть у нас передаётся массив на n элементов из m разрядов и каждая такая цифра принимает значение от 0 до k Тогда T(n + k) мы тратим на сортировку подсчётом и делаем так m раз => T(m(n+k))