String Insertion Sort program

Question

I am just starting to lean C so I don't know it very well. The program we are given tells us to write an Insertion Sort program that takes 20 strings seperated by space and sorts then alphabetically and prints them out in order. This is confusing me greatly since C doesn't have a String data type (at least to my knowledge). Aren't Strings just character arrays? Here is what I got:

#include <stdio.h>
#include <string.h>
#define MAX_STRINGS 20

void InsertionSort(char list[]);

void main()
{
    int index;
    char strings[MAX_STRINGS];

    /* Get input */
    printf("Enter %s strings.\n", MAX_STRINGS);
    for (index = 0; index < MAX_STRINGS; index++)
    {
        char tempString[100];
        printf("Input string %d : ", index);
        scanf("%s", &tempString[0]);
        strings[index] = tempString;
    }

    InsertionSort(strings);

    printf("\nThe input set, in alphabetical order:\n");
    for (index = 0; index < MAX_STRINGS; index++)
    {
        printf("%s\n", strings[index]);
    }
}

void InsertionSort(char list[])
{
    int unsorted;
    int sorted;
    char unsortedItem;

    for(unsorted = 1; unsorted < MAX_STRINGS; unsorted++)
    {
        unsortedItem = list[unsorted];

        for (sorted = unsorted - 1; (sorted >= 0) && (list[sorted] >  unsortedItem); sorted--)
        {
            list[sorted + 1] = list[sorted];
        }
        list[sorted + 1] = unsortedItem;
    }
}

I am completely new to C and C syntax and I find it very confusing. This program is not working correctly. What it is doing is it allows me to enter 20 strings, but then nothing is sorted and it prints out nothing. Any idea on how to fix that? Also, is there any idea to how I can get it to where I type a single sentence and the each string is separated by white space? For example if I type, "I am learning how to program in C and right now I do not like it." that would give me 16 strings. "I", "am", "learning", etc. Thanks.

Answer 1

A few problems with the original code:

1) You cannot copy strings using =; use strncpy for that (using = only assigns pointers).

2) A string is an array of chars; therefore an array of strings is an array of arrays of chars (so your InsertionSort signature is wrong). Note that C strings are null terminated, which simply means that a byte with the value of 0 signifies the end of a string (this is very important, if you forget everything else, remember this).

3) %s expects a char*; this line produces UB: printf("Enter %s strings.\n", MAX_STRINGS);. What you want is %d instead (read up on printf format specifiers).

4) You can't compare strings using normal arithmetic operators; those compare pointers. You need to use strcmp.

5) Your implementation of the insertion sort algorithm was wrong.

6) There are a few versions of main declarations allowed by the standard, and char main isn't one of them. In this case just use int main.

Here is a fixed version of your code:

#include <stdio.h>
#include <string.h>
#define MAX_STRINGS 20
#define MAX_STRING_LEN 200

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN]);

int main()
{
    int index;
    char strings[MAX_STRINGS][MAX_STRING_LEN];

    /* Get input */
    printf("Enter %d strings.\n", MAX_STRINGS);
    for (index = 0; index < MAX_STRINGS; index++)
    {
        printf("Input string %d : ", index);
        scanf("%199s", strings[index]);     // limit the width so we don't go past the buffer
        strings[index][sizeof(strings[index]) - 1] = '\0';
    }

    InsertionSort(strings);

    printf("\nThe input set, in alphabetical order:\n");
    for (index = 0; index < MAX_STRINGS; index++)
    {
        printf("%s\n", strings[index]);
    }
}

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN])
{
    for (int i = 1; i < MAX_STRINGS; i++)
    {
        int j = i;

        while (j > 0 && strcmp(list[j - 1], list[j]) > 0)
        {
            char tmp[MAX_STRING_LEN];
            strncpy(tmp, list[j - 1], sizeof(tmp) - 1);
            tmp[sizeof(tmp) - 1] = '\0';

            strncpy(list[j - 1], list[j], sizeof(list[j - 1]) - 1);
            list[j - 1][sizeof(list[j - 1]) - 1] = '\0';

            strncpy(list[j], tmp, sizeof(list[j]));
            list[j][sizeof(list[j]) - 1] = '\0';

            --j;
        }
    }
}

This might be a bit overwhelming at first, but read it slowly and carefully and you should have no problems.

The = '\0's after strncpy or scanf - these function don't implicitly null-terminate strings, so we have to do that manually - you might get away without doing it a few times, but in the long run it'll get back to you eventually. Stay safe and make it a habit.

Everyone else: if you spot any errors, let me know - it's late and I'm tired.

Regarding your questions in the comments:

1) Why am I starting at 1 in the for loop?
Because I'm later referring to list[j - 1], and with j set to the value of i (initially), it can't be less than 1 or we'd be using negative indices. See here for a description of the algorithm.

2) How to read an entire line of string, including spaces?
The best solution would be to use fgets. Note that it has one quirk: it stores the \n character in the array as well. If you don't want it you'll have to remove it manually.

3) What is tmp for?
This is just a temporary char buffer so I can swap the two strings, as the algorithm requires. This isn't specific to strings, in general to swap two variables you need a third, temporary one (unless you opt for some dirty XOR hacks).

Answer 2

Use this function to sort strings alphabetically:

int s_bubblesortA(int argc,char **argv)
{
    int i , j = 0;
    char *p_1 , *p_2 , *tmp;
    while( j < argc )
    {
        for( i = 0 ; i < argc - j - 1 ; i++ )
        {
            p_1 = argv[i] , p_2 = argv[i+1];
            while( *p_1 && *p_2 )
            {
                if( *p_1 < *p_2 )
                    break;
                else if( *p_1 > *p_2 || ( ! *(p_2 + 1) && ( *p_1 == *p_2 ) && *(p_1+1) ) )
                {
                    tmp = argv[i];
                    argv[i] = argv[i+1];
                    argv[i+1] = tmp;
                    break;
                }
                p_1++;
                p_2++;
            }
        }
        j++;
    }
    return 0;
}

note: check this link to so my full answer to a similar post.sort words alphabeticaly in C