Question

Помогите реализовать сортировку подсчетом в С++ с объяснениями\комментариями

Answer 1

#include <iostream>
#include <vector>
using namespace std; //теперь нам не придется страдать с std::
int main(){
int n; cin>>n; //ввод кол-ва сортируемых элементов
vector <int> a(1e9,0); //создание вектора для хранения ответа. пока он заполнен 0. можно использовать массив
for (int i=0; i<n; ++i) { //запускаем цикл для ввода чисел
int input; cin>>input; //вводим сортируемое число
++a[input]; //считаем кол-во таких элементов во входном файле
}
for (int i=0; i<1e9; ++i) //цикл по всем элементам массива ответа
for (int j=0; j<a[i]; ++j) //цикл, который выводит данный элемент столько раз, сколько он встречается в массиве
cout<<i<<' ';
return 0; //завершение работы программы
}
Сортировка подсчетом заключается в том, что мы считаем, сколько раз данный элемент встречается в сортируеиом массиве и воводим его столько раз подряд на нужном месте, сколько он встречается в массиве.
Написанная мной программа сортирует элементы
$0 \leqslant x \leqslant {10}^{9}$
общее кол-во которых не превосходит
${10}^{9}$
Если нужно что-то еще – пиши. Буду обьяснять более подробно.

Answer 2

Сортировка подсчетом (Counting Sort) - это линейный алгоритм сортировки, который работает для целых чисел или элементов, имеющих определенный диапазон. Он основан на подсчете количества элементов с определенным значением и их последующей перестановке в правильном порядке. Этот алгоритм обладает линейной временной сложностью и может быть очень эффективным на небольших диапазонах целых чисел.

Давайте реализуем сортировку подсчетом в C++:

cppCopy code
#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr) {
    // Найдем максимальное и минимальное значения в массиве, чтобы определить диапазон
    int max_val = arr[0];
    int min_val = arr[0];
    for (int num : arr) {
        if (num > max_val) max_val = num;
        if (num < min_val) min_val = num;
    }

    int range = max_val - min_val + 1;
    std::vector<int> count(range, 0); // Создадим вспомогательный массив для подсчета значений

    // Подсчет количества каждого элемента в массиве
    for (int num : arr) {
        count[num - min_val]++;
    }

    // Восстановление отсортированного массива из вспомогательного массива с учетом количества элементов
    int idx = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[idx++] = i + min_val;
            count[i]--;
        }
    }
}

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    
    std::cout << "Исходный массив: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    countingSort(arr);

    std::cout << "\nОтсортированный массив: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    return 0;
}

Объяснение:

1. Найдем максимальное и минимальное значения в массиве для определения диапазона сортировки.

2. Создадим вспомогательный массив count, который будет использоваться для подсчета количества элементов с каждым значением.

3. Проходим по исходному массиву и инкрементируем соответствующий элемент в массиве count.

4. Восстанавливаем отсортированный массив из вспомогательного массива count, учитывая количество элементов каждого значения.

5. В итоге, исходный массив будет отсортирован по возрастанию.

Сортировка подсчетом может быть эффективной, когда диапазон значений элементов не очень велик, но она требует дополнительной памяти для вспомогательного массива count. Также стоит учитывать, что этот алгоритм не является стабильным (не сохраняет порядок элементов с одинаковыми значениями). Если вам требуется стабильная сортировка, рассмотрите другие алгоритмы, такие как сортировка слиянием.