В каком месте стоит поправить алгоритм сортировки подсчетом, чтобы она корректно работала?

Question

[Матвей]

Подскажите, пожалуйста, на ошибку в коде сортировки - при малом количестве элементов массива сортировка работает либо неккоректно (выводит на экран неотсортированный масси), либо происходит "срабатывание точки останова". При большом количестве элементов N>100 работает корректно, а при малом "барахлит".

где count - количество итераций.

Comments

[Wataru]

Код нельзя вставлять картинкой (пункт 3.8 в правилах). Он должен быть оформлен в тег code (кнопка </> в редакторе).

[Slavik KENNY]

Дай угадаю - в массиве значение до 100?

[Матвей]

Slavik KENNY, нет. Длина массива задаётся пользователем, а затем на основе этого генерируется неотсортированный массив из случайных чисел.

[Sergio]

кстати sizeof(arr) должно быть sizeof(*arr)

[Sergio]

Матвей, Размер массива arr - n и числа в нём от нуля до n, где n задаётся вводом, так?

[mayton2019]

И где вывод результата? Функция поработала с массивом p и тихо его прибила внутри себя.

[Матвей]

mayton2019, это часть функции, вывод в этой же функции, только ниже (не стал прикреплять, потому что вывод работает правильно, а вот алгоритм как-то не очень). Также функция сортировки вызывается в main в switch.

[Матвей]

Sergio, Sergio, генерируется рандомный массив, состоящий из n элементов, n задаётся вводом. Числа массива могут принимать значение от 0 до 10000.

[Gnifajio None]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void countSort(vector<int>& arr)
{
    int maxElement = *max_element(arr.begin(), arr.end());
    int minElement = *min_element(arr.begin(), arr.end());
    int range = maxElement - minElement + 1;

    vector<int> count(range), output(arr.size());
    for (int i = 0; i < arr.size(); i++)
        count[arr[i] - minElement]++;

    for (int i = 1; i < count.size(); i++)
        count[i] += count[i - 1];

    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minElement] - 1] = arr[i];
        count[arr[i] - minElement]--;
    }

    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

int main()
{
    vector<int> arr = { 4, 3, 2, 1, 5, 6, 7, 8, 9 };
    countSort(arr);

    for (int i : arr)
        cout << i << " ";
    cout << endl;

    return 0;
}