массивы — C ++: сортировка строк с использованием сбоя сортировки радиуса LSD
Я написал некоторый код, предназначенный для сортировки массива строк с использованием сортировки по основанию, начиная с наименее значащей цифры. Эта функция предполагает, что все строки имеют одинаковую длину, а каждый символ в нижнем регистре.
Я сталкиваюсь со сбоями всякий раз, когда попадаю в цикл, в котором я присваиваю значения временному массиву. Вы можете увидеть мою функцию здесь:
#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
Я предполагаю, что у меня есть недостатки в логике, но я не могу понять это для моей жизни.
Решение
После второго цикла count [0] должен быть равен нулю, а в третьем цикле отсутствует -97. В этом примере решается проблема с использованием счетчика размера 27 вместо 26. В первом цикле в этом примере используется -96, поэтому count [0] = 0, count [1] = # экземпляров ‘a’s, 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;
}
Другие решения