arrayscsortingcounting-sort

How to implement Counting Sort to sort an array of char in C?


So, I'm trying to implement the Counting Sort algorithm to sort an array of digits given by the user, here's my code:

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

int main()
{
    int i,n=15;
    char arr[]={"ABEFGEAGCEDBFAC"}; //I'm using this string to test it out
    /*for(int i=0; i<n; i++){
        printf("Insert a letter %d: ",i+1);
        scanf("%c",&arr[i]);
        fflush(stdin);
    }
    */
    printf("Array: \n[ ");
    for(i=0; i<n; i++){
        if(i<n-1)
            printf("%c | ",arr[i]);
        if(i==n-1)
            printf("%c ]\n",arr[i]);
    }
    printf("\n");
    int range[7];
    for(i=0;i<7;i++){
        range[i]=0;
    }
    for(i=0; i<n; i++){ //I've seen other ways to do this, but I just need it to go from A-G
                        //not sure if this is the problem.
        switch(arr[i]){
            case 'A':
                range[0]++;
                break;
            case 'B':
                range[1]++;
                break;
            case 'C':
                range[2]++;
                break;
            case 'D':
                range[3]++;
                break;
            case 'E':
                range[4]++;
                break;
            case 'F':
                range[5]++;
                break;
            case 'G':
                range[6]++;
                break;
        }
    }

    printf("Counting array (number of times it appear in the array): \n[ ");
    for(i=0; i<7; i++){
        if(i<6)
            printf("%d | ",range[i]);
        if(i==6)
            printf("%d ]\n",range[i]);
    }
    printf("\n");

    for(i=1;i<7;i++){ //Here I do the sum of all elements in the array
        range[i] = range[i] + range[i-1];
    }

    printf("Sum of the array: \n[ ");
    for(int i=0; i<7; i++){
        if(i<6)
            printf("%d | ",range[i]);
        if(i==6)
            printf("%d ]\n",range[i]);
    }
    printf("\n");
    char ord[15];

    for(i=n-1;i>=0;i--)
        ord[--range[arr[i] - 'A']] = arr[i];
    for (i=0;i<n;i++){
        printf("%c ",ord[i]);
    }
/*
    printf("Ord: \n[ ");
    for(int i=0; i<15; i++){
        if(i<14)
            printf("%c | ",ord[i]);
        if(i==14)
            printf("%c ]\n",ord[i]);
    }
*/
}

So, as you can see, if I'm not wrong, the error is when I try to put each letter in its correct position using the range array in the second to last for sentence. I've seen other ways to implement it but I just can't get it done, it's crashing as soon as I try to print ord[i]. I'm having trouble trying to fully understand what's going on in that for.

Update:
Tried to implement fish-404's corrections on the code as shown above. Can't get it properly implemented.

Last Update:
Code above is now finished and fully functional. Thanks to @fish-404 .


Solution

  • In this line, arr[i] is a char, you try to use char as the array range index.

    ord[range[arr[i]]] = arr[i];
    

    Update

    If I get you correctly, I think you want use the arr[i] char as a index to search in range array.

    As you can see, the range array you use count the letter, to use the letter to index, you just use arr[i]-'A' to count the letter order in the range array.

    for (i = n; i >= i; i--)
      ord[--range[arr[i] - 'A']] = arr[i];
    
    // use this to see result
    for (i = n;i >= 1; i--)
      printf("i: %d, ord[i]: %c\n", i, ord[i-1]);