Sorting an array of strings using pointers (followup)

Question

This is a follow-up to this post.

Things I've changed:

1. The number of strings is checked.
2. I'm using pointers now.

I'll use fgets in more mission critical situations. For a lab assignment, the scanf approach will suffice I hope.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 100
#define WID 80

void sort(char *s[], int n);

void display(char *s[], int n);

int main()
{
    int n, i;
    char *s[LEN];
    printf("Enter number of strings : ");
    scanf("%d", &n);
    printf("Enter strings one by one :\n");
    if (n > LEN) {
        printf("Sorry, maximum strings allowed is %d. Defaulting.", LEN);
        n = LEN;
    }
    for (i = 0; i < n; i++) {
        printf("%d : ", i + 1);
        s[i] = (char *) malloc(WID * sizeof(char));
        scanf(" %s", s[i]);
    }

    printf("The initial elements are:\n");
    display(s, n);
    sort(s, n);
    printf("The elements after sorting are:\n");
    display(s, n);

    return 0;
}

void sort(char *s[], int n)
{
    char *temp;
    int item, i;

    for (item = 1; item < n; item++) {
        temp = s[item];
        for (i = item; i > 0 && strcmpi(s[i - 1], temp) > 0; i--);
        memcpy(&s[i + 1], &s[i], (item - i) * sizeof(char *));
        s[i] = temp;
    }
}

void display(char *s[], int n)
{
    int i;
    printf("\n\n");
    for (i = 0; i < n; i++) {
        printf("%s ", s[i]);
    }
    printf("\n\n");
}

Any alternative or more elegant approach is welcome.

Answer 1

It's not necessary to cast the result of malloc(). A void* can be assigned to any other kind of pointer in C, so write

        s[i] = malloc(WID); // no need to multiply by sizeof (char) -
                            // that's 1, by definition

However, it is necessary to test that the result of malloc() is not null:

        s[i] = malloc(WID);
        if (!s[i]) {
            fprintf(stderr, "malloc failed\n");
            return EXIT_FAILURE;
        }

I would recommend swapping the order of the following outputs, as the feedback on the number of inputs belongs before the instruction to start entering values. I'd write

if (n > LEN) {
    printf("Sorry, maximum strings allowed is %d. Defaulting.", LEN);
    n = LEN;
}
printf("Enter strings one by one :\n");

I didn't fully read the algorithm of your sort() (I recommend you learn to use the Standard Library qsort(), but perhaps you want to experiment with algorithms?); however, I would note as a style issue that if you use a for loop with an empty statement, it's helpful to put the empty statement on its own line, thus:

        for (i = item;  i > 0 && strcmpi(s[i-1], temp) > 0;  i--)
            ;

This makes it more obvious to the reader that the following statement is not part of the loop. It may also be worth a comment to indicate that the empty statement is intentional, as an accidental stray ; is a common mistake.

Answer 2

Bad use of memcpy

Your call to memcpy() uses two pointers with overlapping memory:

    memcpy(&s[i + 1], &s[i], (item - i) * sizeof(char *));

I'm surprised that your program even works at all because memcpy() normally doesn't work properly in a situation like that. You should be using memmove() instead.

Here is some further reading if you need more information on memcpy vs memmove.

Addendum

I built and ran your program. It uses the nonstandard strcmpi() function, which leads me to believe you are using a Microsoft based compiler. This might explain why your program works for you (because the Microsoft memcpy() deals with overlapping memory correctly).

I replaced strcmpi() with strcasecmp() and built with gcc, and this is the result when I ran your program:

Enter number of strings : 5
Enter strings one by one :
1 : e
2 : d
3 : c
4 : b
5 : a
The initial elements are:


e d c b a

The elements after sorting are:


a b b b b

Notice how the array got corrupted to be a b b b b due to the overlapping memcpy().

Answer 3

Advice 1

I suggest that you add the { and } to loop/conditional block even in the case it's a one-liner. The reason is if someone maintains your code and need to add a statement or a couple, they do not need to type those.

Advice 2

The display may print a more friendly text:

void display(char *s[], int n)
{
    int i;
    printf("\n\n[");
    const char* separator = "";
    for (i = 0; i < n; i++) {
        printf("%s%s", separator, s[i]);
        separator = ", ";
    }
    printf("]\n\n");
}

For example: [abc, bb, def].

Advice 3

If you need to sort large array of strings, there are more efficient algorithms especially for sorting strings. See this. Also, I believe radix sort would perform good as well.

Hope that helps.

Answer 4

First suggestion

    printf("Enter number of strings : ");
    scanf("%d", &n);
    printf("Enter strings one by one :\n");
    if (n > LEN) {
        printf("Sorry, maximum strings allowed is %d. Defaulting.", LEN);
        n = LEN;
    }

• Your message about the number of strings really belongs before the prompt to enter the strings.
• You also want to check that scanf succeeded. What you do with that information is up to you, but keep in mind that if scanf didn't successfully scan an integer, it'll leave the bad input in the buffer to be read by scanf again. You may wish to use fgets to read a whole line, then use something like sscanf to extract the integer you're looking for.

Second suggestion

    for (i = 0; i < n; i++) {
        printf("%d : ", i + 1);
        s[i] = (char *) malloc(WID * sizeof(char));
        scanf(" %s", s[i]);
    }

• i can be locally scoped to the loop.
• Check to ensure malloc succeeded. I would put this before any I/O as there's no point in printing a prompt if the allocation failed.
• Again, check to ensure scanf succeeded.
• Your string can only store WID chars, but you don't specify a width for the %s format specifier. This can run into a buffer overflow situation, meaning your "string" might not be null-terminated, resulting in undefined behavior when used with the %s format specifier in printf.
• Better would be to use fgets to limit the input and remove the potential for UB.

Memory

You should free the memory you've dynamically allocated.