Quicksort a 2D strings array in C

Question

I am using quick sort algorithm to sort the strings in a 2D array. It works for most of the case but I don't know why the code doesn't work for this case. I had look through many similar questions about quick sort in SO but I still can't figure out what is the problem.

Expected output:

Apple
London
Switch
Table
The

Actual Output:

Apple
London
Table
Switch
The

Here's my code:

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

void quickSort(char arr[][20], int left, int right);

int main(void)
{
    int i;
    char str[][20] = { "Table", "Apple", "The", "Switch", "London"};

    printf("Before:\n");
    for(i=0; i<5; i++) {
        printf("%s\n", str[i]);
    }
    printf("\n");

    quickSort(str, 0, 4);

    printf("After sort:\n");
    for(i=0; i<5; i++) {
        printf("%s\n", str[i]);
    }
    return 0;
}

void quickSort(char arr[][20], int left, int right)
{
    int i, j;
    char *x;
    char tmp[20];

    i = left;
    j = right;
    x = arr[(left + (right - left)) / 2];

    while(i <= j)
    {
        while((strcmp(arr[i],x) < 0) && (i <= right) && (j > i)) {
            i++;
        }
        while((strcmp(arr[j],x) > 0) && (j >= left) && (j >= i)) {
            j--;
        }
        if(i <= j) {
            strcpy(tmp, arr[i]);
            strcpy(arr[i], arr[j]);
            strcpy(arr[j], tmp);
            i++;
            j--;
        }
    }

    if(left < j) {
        quickSort(arr, left, j);
    }
    if(i < right) {
        quickSort(arr, i, right);
    }
}

This line from your implementation x = arr[(left + (right - left)) / 2]; looks weird. You only keep a pointer to a string while later you copy the strings. And I cannot remember seeing a line like that in common implementations... Looks like you should rewrite yours... — Serge Ballesta
– Serge Ballesta, Commented Feb 23, 2021 at 13:34
@anastaciu I dont know anything about qsort, but thanks for your suggestion. I will try to use it. — yuncf
– yuncf, Commented Feb 23, 2021 at 13:36
@SergeBallesta I used x = arr[(left + right) / 2]; at first, but then I found some codes using this instead — yuncf
– yuncf, Commented Feb 23, 2021 at 13:37
@yuncf: what we mean is that if you want to use the median as a pivot, you should strcpy it to make sure that the pointed data is not altered. — Serge Ballesta
– Serge Ballesta, Commented Feb 23, 2021 at 13:56

Any Day · Accepted Answer · 2021-02-23 14:35:03Z

1

As mentioned, there's a qsort function in C that you can use. Just calculate the size of your array and pass the strcmp function as the 4th argument.


    size_t n = sizeof(str)/sizeof(str[0]);
    qsort(str, n, sizeof(str[0]), (int (*)())strcmp);

Hope that helped!

edited Feb 23, 2021 at 14:35

answered Feb 23, 2021 at 14:05

Any Day

4183 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Any Day Over a year ago

Ah, thanks.. I'm kinda new to C myself, and when I was using qsort myself, it seemed to want me to cast to Void.

Any Day Over a year ago

Thanks, really appreciate it. Here's the warning I seem to get. expected 'int (*)(const void *, const void *)' but argument is of type 'int (*)(const char *, const char *)'

Any Day Over a year ago

Oh, no! Your solution works, I added it to the answer because I figure you probably know better than me.

chux · Accepted Answer · 2021-02-23 15:48:10Z

0

I don't know why the code doesn't work for this case

Mid point incorrectly calculated:

x = arr[(left + (right - left)) / 2]; // Oops
// This is same as
x = arr[right/2]; // Oops

Use

x = arr[left + (right - left)/2];  // Fixed

Avoid

x = arr[(left + right)/2]; // left + right may overflow

With any type: left, right, left + (right - left)/2 does not overflow when left <= right.

With int left, int right, left + (right - left)/2 does not overflow when values are positive.

Perhaps other issues too.

edited Feb 23, 2021 at 15:48

answered Feb 23, 2021 at 15:34

chux

158k17 gold badges160 silver badges311 bronze badges

Collectives™ on Stack Overflow

Quicksort a 2D strings array in C

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related