Thread: Radix Sort ( + counting sort) does not stable sort.

Hello, i have a small problem with sorting "stable" with radix-sort + counting-sort. While on paper it sorts stable (all elements with same values before and after sorting have same order), after running my program, it doesn't sort this way at all, and i have no idea why.

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 3
#define ILE 5




char **As = NULL;
char **Bs = NULL;
char **T = NULL;
int lengthA;        //= strlen(As[0]);


size_t lenA[ILE];


int place[ILE];


int getK(int j){
    int k = 0, i;   //, j;
    for(i = 0; i < MAX; i++){
        if((int)As[j][i] > k){
            k = (int)As[j][i];
        }
    }


    return k;
}


void CSort(int p){


    int k = 123;
    int C[k];
    int i;


    for(i = 0; i < k; i++){
        C[i] = 0;
    }


    for(i = 0; i < ILE; i++){
        C[(int)As[i][p]]++;
    }


    for(i = 1; i < k; i++){
        C[i] = C[i] + C[i - 1];
    }


    for(i = 0; i < ILE; i++){
        Bs[C[(int)As[i][p]] - 1] = As[i];
        printf("As[%i][%i] == %c ", i, p, As[i][p]);
        printf("C[%i] == %i ", (int)As[i][p], C[(int)As[i][p]]-1);
        printf("  Bs[%i]  == %s \n", C[(int)As[i][p]] - 1, Bs[C[(int)As[i][p]] - 1]);


        //(As[i], Bs[C[(int)As[i][p]]], sizeof(As[i]));
        C[(int)As[i][p]]--;
    }




}


void RSort(int d){
    int i;
    for(i = d; i >= 0; i--){
        CSort(i);
        memcpy(As, Bs, sizeof(*As) * ILE);
        //memset(Bs, 0, ILE*MAX);
        puts("wykonane!");
    }
}


void wczytaj(){
    //	FILE *f = fopen("nazwiskaASCII", "r");
    FILE *f = fopen("plik", "r");
    int i;
    char tmp[MAX];
    int len;
    for(i = 0; i < ILE; i++){
        //	 fscanf(f, "%i", &place[i]);
        fscanf(f, "%s", tmp);
        len = strlen(tmp);
        As[i] = (char*)malloc(sizeof(char)*MAX);
        Bs[i] = (char*)malloc(sizeof(char)*MAX);
        strcpy(As[i], tmp);
        strcpy(Bs[i], tmp);
        lenA[i] = len;


    }
    printf("Wczytano prawidlowo!\n");
    fclose(f);
}
void wyswietl(char **a){
    int i;
    for(i = 0; i < ILE; i++){
        //int k = getK(i);
        printf("%i. %s  \n",i,  a[i]); //, lenA[i], k);
    }
    printf("\n");


}
void zapisz(){
    FILE *f = fopen("nazwiskaSORTED", "w");
    int i;
    for(i = 0; i < ILE; i++){
    //	fprintf(f, "%i\t%s\n",place[i], As[i]);
        fprintf(f, "%s \n", Bs[i]);
    }


    fclose(f);
    printf("Zapisano pomyslnie!\n");
}




int main(void){
    //system("./slowo");
    //int i;
    //As = (char**)malloc(ILE*sizeof(char*));
    As = malloc(sizeof(*As) * ILE);
    Bs = malloc(sizeof(*As) * ILE);
    //Bs = (char**)malloc(ILE*sizeof(char*));
    T  = malloc(sizeof(*As) * ILE);
    //memcpy(T, As, sizeof(*As) * ILE);
    wczytaj();
    memcpy(T, As, sizeof(*As) * ILE);
    //memset(Bs, 0, ILE*10);
    //int k = getK(0);
    lengthA = strlen(As[0]);


    printf("\n");


    printf("org\n");
    wyswietl(As); // shows table AS
    wyswietl(Bs);
    //RSort(0);
    CSort(1);
    memcpy(As, Bs, sizeof(*As) * ILE);
    //wyswietl(T); // shows table AS
    wyswietl(As);
    wyswietl(Bs);
    CSort(0);
    wyswietl(Bs);
    //wyswietl(T);
    //wyswietl(Bs);






    //zapisz();
    //	free(As);
    //	free(Bs);


    return 0;
}

My two sorting functions, and the "ILE" stands for number of words to sort. In my `main()` i malloc memory without any problems.

What i expect is to have sorted list of strings and instead of

Code:

ab, bb, bc, ca, cd

I have:

Code:

ab, bc, bb, cd, ca

No idea why, so i am asking for some help, thanks in advance!


Edit: Added full code.
@rcgldr: I am using -- because I am going from 0 not from max value.

@anduril462: well, i am from Poland, so I am naming variables mostly in polish language. Also, what i meant in "no problem" was no compiler errors :P.

@laserlight: thanks! didn't notice earlier, fixed.

It would help if you posted the code for the entire program.

By the way, you're accessing your variable length array out of bounds because the condition expression of two of your loops is i <= k instead of i < k.

CSort() is generating and using the indexes in C[] in reverse order, you need to change the last for statement in CSort() to:

for(i = ILE-1; i >= 0; i--){

Also as laserlight mentioned, you need to use i < k in the other two for loops. Note that k = 123 assumes the largest character value is 'z' (decimal 122). You could set k = 256 to handle any 8 bit character value.