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

  1. #1
    Registered User
    Join Date
    Nov 2013
    Posts
    2

    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.
    Last edited by siepet; 11-26-2013 at 11:05 AM. Reason: added code

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    It would help if you posted the code for the entire program.
    Last edited by rcgldr; 11-26-2013 at 11:05 AM.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    Please post the complete program, or at least enough of it for us to compile and test with. Saves us from having to write a bunch of code just to test your program, and for all we know, you have a bugs in your other functions too. You say you malloc with no problem, but we get claims like that on this board all the time that turn out to be wrong (no offense). Plus, you must do more than just malloc in main.

    Also, why use an obscure name like ILE for the number of words, that you must explain each time, instead of a clear name like NUM_WORDS?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,922
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    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.
    Last edited by rcgldr; 11-26-2013 at 11:49 AM.

  6. #6
    Registered User
    Join Date
    Nov 2013
    Posts
    2
    @rcgldr: oh, thanks! it is weird, because that would be the last place i would look, but my CSort for numbers has it correctly - going down. As to accessing array, I have changed it to i < k. Thank you guys for help! Turns out, it was rather silly mistake! Thanks again.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Quote Originally Posted by siepet View Post
    @rcgldr: oh, thanks! it is weird, because that would be the last place i would look, but my CSort for numbers has it correctly - going down. As to accessing array, I have changed it to i < k. Thank you guys for help! Turns out, it was rather silly mistake! Thanks again.
    In this case your sort is ascending (going up). I assume you number sort was descending (going down).

    The alternative is to setup C for ascending sequences:

    Code:
    void CSort(int p){
        int k = 123;
        int C[k];
        int i, m, n;
    
        for(i = 0; i < k; i++){
            C[i] = 0;
        }
    
        for(i = 0; i < ILE; i++){
            C[(int)As[i][p]]++;
        }
    
        n = 0;
        for(i = 0; i < k; i++){
            m = C[i];
            C[i] = n;
            n += m;
        }
    
        for(i = 0; i < ILE; i++){
            Bs[C[(int)As[i][p]]] = As[i];
            printf("As[%i][%i] == %c ", i, p, As[i][p]);
            printf("C[%3i] == %3i ", (int)As[i][p], C[(int)As[i][p]]);
            printf("  Bs[%i]  == %s \n", C[(int)As[i][p]], Bs[C[(int)As[i][p]]]);
            C[(int)As[i][p]]++;
        }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. radix sort
    By rcgldr in forum C Programming
    Replies: 9
    Last Post: 08-20-2013, 05:44 PM
  2. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM
  3. Can counting sort sort in descending order?
    By Nutshell in forum C Programming
    Replies: 3
    Last Post: 03-06-2003, 09:59 AM
  4. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM
  5. Radix sort.
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 09-09-2001, 04:48 AM