Home > Mobile >  Bubble sort on string array not doing anything in C with strcmp
Bubble sort on string array not doing anything in C with strcmp

Time:05-07

I am trying to sort a string array in C (char**), the string array is an array of all the names of files in a directory. Here are all the parts of the code, I expect the code to sort the array alphabetically, but it doesn't work. Here is the code to get the files from the directory

typedef struct
{
    char** names;
    int32_t count;
} Files;

void swap(char* a, char* b)
{
    char* temp = a;
    a = b;
    b = temp;
}

void bubbleSort(char** strs, uint32_t length)
{
    uint32_t i = 0, j = 0;
    for (i = 0; i < length; i  )
    {
        for (j = 0; j < length - i - 1; j  )
        {
            if (strcmp(strs[j], strs[j   1]) < 0)
            {
                swap(strs[j], strs[j   1]);
            }
        }
    }
}

Files* getScannableFilesInDir(char* dirname)
{
    Files* files = (Files*)malloc(sizeof(Files));
    files->names = NULL; //clearing garbage values
    files->count = 0;    //clearing garbage values
    uint32_t dirnameLength = strlen(dirname);
    uint32_t count = 0;
    uint32_t countIterations = 0;
    DIR* d = opendir(dirname);
    struct dirent* dir = NULL;
    while ((dir = readdir(d)) != NULL)
    {
        if (files->names == NULL) //first file, if START_AMOUNT is set to 0 we want to allocate enough space for the first path, once we know there is at least 1 file
        {
            files->names = (char**)malloc(1 * sizeof(char*));
            count  ; // there is enough space allocated for 1 string 
        }

        if (strcmp(dir->d_name, ".") && strcmp(dir->d_name, "..") && dir->d_type != DT_DIR)
        {
              countIterations;
            if (count < countIterations)
            {
                files->names = (char**)realloc(files->names, countIterations * sizeof(char*)); //adding 1 more space
            }
            files->names[countIterations - 1] = (char*)malloc(sizeof(char) * (strlen(dir->d_name)   dirnameLength)   2); //-1 because we are incrementing at the start of the loop and not the end 
            //  2 at the end because a. the \0 at the end, b. 1 space for adding the slash
            strcpy(files->names[countIterations - 1], dirname);
            files->names[countIterations - 1][dirnameLength] = '/'; //changing the \0 to /
            strcpy(files->names[countIterations - 1]   (dirnameLength   1), dir->d_name); //adding the name after the /, now we have the full name
        }
    }
    closedir(d);
    files->count = countIterations;
    bubbleSort(files->names, files->count);
    return files;
}

I checked the rest of the code, I am not changing the value of the files->names at any other point of the code, just reading it.

CodePudding user response:

You swap, and the way it is invoked from bubblesort, are both wrong. First let me educate you on a simple fundamental.

Arguments in C are pass-by-value. The only way to change caller-side data from an argument passed to a function as a parameter is to change the fundamentals of the parameter. You'll still pass by-value, you just need to make the "value" something you can use to access the caller's variable data. In C, you do that by declaring the formal parameter to be a pointer-to-type, pass the address of the thing you want changed caller-side, and within the function use the pointer via dereference to instigate the change.

void foo(int *a)
{
    *a = 42; // stores 42 in whatever 'a' points to
}

Now, lets take a look at your swap:

void swap(char* a, char* b)
{
    char* temp = a;
    a = b;
    b = temp;
}

Well, we have two pointers. But nowhere in this code do we actually dereference anything. All we're doing is swapping the values of the two pointers locally. The caller is completely unaffected by any of this.

What your swap is supposed to be doing is swapping two pointers. We have two char* caller side values we want to swap. The way to do that is exactly as we discussed before. Declare the formal parameters to be pointer-to-type (our type is char*, so our parameters are char**), then use dereferencing to modify the caller-side data.

void swap(char **ppA, char **ppB)
{
    char *pp = *ppA;
    *ppA = *ppB;
    *ppB = pp;
}

That will swap two pointers, but only if the caller passes us the addresses of the two pointers. Note the vernacular here. I did not say "passes us the addresses in the two pointers" (e.g. their values), I said "passes us the addresses of the two pointers" (e.g. where the pointers themselves reside in memory). That means bubblesort needs changing too:

void bubbleSort(char** strs, uint32_t length)
{
    uint32_t i = 0, j = 0;
    for (i = 0; i < length; i  )
    {
        for (j = 0; j < length - i - 1; j  )
        {
            if (strcmp(strs[j], strs[j   1]) < 0)
            {
                swap(strs j, strs j 1); // <=== HERE
            }
        }
    }
}

This passes the addresses of the pointers at str[j] str[j 1] to the swap function.

That should solve your swap issue. Whether the algorithm is correct, or for that matter the rest of your code, I leave to you to digest.

  • Related