Нарушается устойчивость LSD сортировки. Помогите исправить

Question

Написал LSD сортировку для строк из строчных букв латинского алфавита, но нарушается устойчивость и строки, начинающиеся с одинакового символа, стоят в обратном порядке.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

int main(){
system("chcp 1251");
srand(time(NULL));
char **x,**y,b;
int n,m,i,j,k,*c,*p;
printf("Количество слов:\n");
scanf("%d", &n);
printf("Длина каждого слова:\n");
scanf("%d", &m);
x = (char**)malloc(sizeof(char*)*n);
for (i = 0; i < n; i++) x[i] = (char*)malloc(sizeof(char)*m);
y = (char**)malloc(sizeof(char*)*n);
for (i = 0; i < n; i++) y[i] = (char*)malloc(sizeof(char)*m);
c = (int*)calloc(26,sizeof(int));
p = (int*)malloc(sizeof(int)*26);
printf("Сформированный массив строк :\n");
for (i = 0; i < n; i++){
    for (j = 0; j < m; j++){
        x[i][j] = rand()%(122-97)+98;
        printf("%c",x[i][j]);   
    }
    printf("\n");   
}
for (j = m - 1; j >= 0; --j){
    for (i = 0; i < n; i++){
        c[x[i][j]-97]++;
    } 
    //for (i = 0; i < 26; i++) printf("%d ", c[i]);
    //printf("\n");
    p[0] = c[0];
    for (i = 1; i < 26; i++){
        p[i] = p[i - 1] + c[i];
        //printf("%d ",p[i]);               
    } 
    //printf("\n");                 
    for (i = 0; i < n; i++){
        y[--p[x[i][j] - 97]] = x[i];
    }
    for (i = 0; i < n; i++){
        x[i] = y[i];
    }
    for (i = 0; i < n; i++){
        c[x[i][j]-97] = 0;
    }   
}
printf("Отсортированный массив строк :\n"); 
for (i = 0; i < n; i++){
    for (j = 0; j < m; j++){
        printf("%c",x[i][j]);   
    }
    printf("\n");   
}
return 0;
}

Answer 1

По мере заполнения массива y следующий элемент из x[] должен браться после последнего использованного с той же буквой, поэтому --p[x[i][j] - 97] должно быть заменено на постинкремент. Из-за этого была инверсия при работе с не последним знаком.

Для обеспечения правильного порядка первый элемент p[] должен быть нулевым, а остальные - кумулятивная сумма c[], за исключением последнего элемента c
(в общем-то p[] и не нужен, можно в c[] всё сделать, запоминая текущий элемент)

p[0] = 0;
for (i = 1; i < 26; i++){
    p[i] = p[i - 1] + c[i - 1];
    //printf("%d ",p[i]);               
} 
//printf("\n");                 
for (i = 0; i < n; i++){
    y[p[x[i][j] - 97]++] = x[i];
}


Result (использовано 8 символов)
afef
babc
bcha
dfch
efdd
fghf
ghde
hadg
hdda
hded

БЛОГ НА HUSL

Нарушается устойчивость LSD сортировки. Помогите исправить

Ответы (1 шт):