C++: Сортировка строк с использованием сортировки сортировки LSD radix

Question

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

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

#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

После второго цикла счетчик [0] должен быть равен нулю, а в третьем цикле отсутствует -97. В этом примере исправлена ​​проблема с использованием Count размером 27 вместо 26. В первом цикле в этом примере используется -96, поэтому count [0] = 0, count [1] = # экземпляров 'a, count [2] = # экземпляров of 'b's, .... 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; 
} 

Если размер графа [] должен быть 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; 
     }