c ++ считая сортировку

Question

Я пытался написать счетчик сортировки, но с ним возникла какая-то проблема.

вот код:

int *countSort(int* start, int* end, int maxvalue)
{
    int *B = new int[(int)(end-start)];
    int *C = new int[maxvalue];

    for (int i = 0; i < maxvalue; i++) 
    { 
        *(C+i) = 0; 
    }
    for (int *i = start; i < end; i++) 
    { 
        *(C+*i) += 1; 
    }
    for (int i = 1; i < maxvalue-1 ; i++) 
    { 
        *(C+i) += *(C+i-1); 
    } 
    for (int *i = end-1; i > start-1; i--) 
    { 
        *(B+*(C+(*i))) = *i; 
        *(C+(*i)) -= 1; 
    }
    return B;   
}

В последнем цикле выдается исключение «Принимает нарушение записи в местоположении: -некоторый адрес оперативной памяти - "

Где я ошибся?

Answer 1

for (int i = 1; i < maxvalue-1 ; i++) 

Это неверная верхняя граница.Вы хотите перейти от 1 к maxvalue.

for (int *i = end-1; i > start-1; i--) 
{ 
    *(B+*(C+(*i))) = *i; 
    *(C+(*i)) -= 1; 
}

Этот цикл также совершенно неверен.Я не знаю, что он делает, но краткий ментальный тест показывает, что первая итерация устанавливает элемент B по индексу значения последнего элемента в массиве на количество раз, которое он показывает.Я гарантирую, что это не правильно.Последний цикл должен выглядеть примерно так:

int* out = B;
int j=0; 
for (int i = 0; i < maxvalue; i++) {  //for each value
    for(j<C[i]; j++) {                //for the number of times its in the source
        *out = i;                     //add it to the output
        ++out;                        //in the next open slot
    }
}

В качестве заключительной ноты, почему вы играете с такими указателями?

*(B + i)  //is the same as
B[i]      //and people will hate you less

*(B+*(C+(*i))) //is the same as
B[C[*i]]  

Answer 2

Так как вы все равно используете C ++, почему бы не упростить код (резко), используя std::vector вместо динамически распределяемых массивов (и утечку одного в процессе)?

std::vector<int>countSort(int* start, int* end, int maxvalue)
{
    std::vector<int> B(end-start);
    std::vector<int> C(maxvalue);

    for (int *i = start; i < end; i++) 
        ++C[*i];

// etc.

Кроме этого, логика, которую вы используете, не имеет смысла для меня. Я думаю, чтобы получить рабочий результат, вам, вероятно, лучше всего сесть с листом бумаги и решить, какие шаги вам нужно использовать. Я оставил счетную часть выше, потому что считаю, что многое правильно. Я не думаю, что остальное действительно так. Я даже дам довольно простую подсказку: как только вы закончите подсчет, вы можете сгенерировать B (ваш результат), основываясь на только на том, что у вас есть в C - вы делаете не нужно вообще ссылаться на исходный массив. Самый простой способ сделать это, как правило, использовать вложенный цикл. Также обратите внимание, что, вероятно, проще reserve пробел в B и использовать push_back для помещения данных в него, а не устанавливать его начальный размер.