C++: сортировка строк с использованием сбоя сортировки радиуса LSD

Question

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

Я сталкиваюсь со сбоями всякий раз, когда попадаю в цикл, в котором я присваиваю значения временному массиву. Вы можете увидеть мою функцию здесь:

#ifndef RADIX_H
#define RADIX_H

#include <string>
#include <iostream>
using namespace std;

void lsd_string_radix(string array[], int array_size, int max_chars)
{
    string *temp = new string[array_size];

    for(int i = max_chars - 1; i >= 0; i--)
    {
        int count[26] = {0};

        for(int j = 0; j < array_size; j++)
        {
            count[static_cast<int>(array[j][i]) - 97]++;
        }

        for(int j = 1; j <= 26; j++)
        {
            count[j] += count[j - 1];
        }

        for(int j = 0; j < array_size; j++)
        {
            temp[count[static_cast<int>(array[j][i])]++] = array[j]; // crashes here
        }

        for(int j = 0; j < array_size; j++)
        {
            array[j] = temp[j];
        }
    }
}

#endif

Я предполагаю, что у меня плохая логика, но я не могу понять это ради своей жизни.

Answer 1

После второго цикла count[0] должен быть равен нулю, а в третьем цикле отсутствует -97. В этом примере решается проблема с использованием счетчика размера 27 вместо 26. В первом цикле в этом примере используется -96, поэтому count[0] = 0, count[1] = # экземпляров 'a, count[2] = # экземпляров из "б",.. . count[26] = # экземпляров 'z', но он используется только в первом цикле. В этом нет необходимости, но проще поместить число 'z' вместо добавления оператора if, чтобы избежать сохранения счетчика в count[26].

#include<iomanip>
#include<iostream>
#include <string>

using namespace std;

void lsd_string_radix(string array[], int array_size, int max_chars)
{
    string *temp = new string[array_size];

    for(int i = max_chars - 1; i >= 0; i--)
    {
        int count[27] = {0};

        for(int j = 0; j < array_size; j++)
            count[static_cast<int>(array[j][i]) - 96]++;

        for(int j = 2; j < 26; j++)
            count[j] += count[j - 1];

        for(int j = 0; j < array_size; j++)
            temp[count[static_cast<int>(array[j][i]) - 97]++] = array[j];

        for(int j = 0; j < array_size; j++)
            array[j] = temp[j];
    }
}

int main()
{
string a[6] = {"mnop", "ijkl", "efgh", "uvwx", "qrst", "abcd"};
    lsd_string_radix(a, 6, 4);
    for(size_t i = 0; i < 6; i++)
        cout << a[i] << endl;
    return 0;
}

Если размер count [] должен быть 26, первый цикл необходимо изменить:

        for(int j = 0; j < array_size; j++){
            if(array[j][i] == 'z')continue;
            count[static_cast<int>(array[j][i]) - 96]++;
        }

или первые два цикла модифицируются:

        for(int j = 0; j < array_size; j++)
            count[static_cast<int>(array[j][i]) - 97]++;

        int m = 0;
        int n;    
        for(int j = 0; j < 26; j++){
            n = count[j];
            count[j] = m;
            m += n;
        }