0

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.

Improve this question
15
  • What is the proper declaration of main? Commented Nov 15, 2015 at 20:36
  • Well, on some platforms an executable can only return exit codes between 0 and 255, so char is fitting ;-) Commented Nov 15, 2015 at 20:36
  • There are enough different things wrong with this that I don't think we can usefully help you. You need a one-on-one coaching session. Please take this question to whoever is teaching you the language. Commented Nov 15, 2015 at 20:37
  • "Aren't Strings just character arrays?". No, strings are char arrays terminated with a '\0' character. This is a very important distinction; if you forget the end delimiter, it will break things. Commented Nov 15, 2015 at 20:37
  • please check my answer in stackoverflow.com/questions/33583221/… Commented Nov 15, 2015 at 20:38

2 Answers 2

Reset to default
4

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).

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

10 Comments

Okay, I am going over the code line for line to try to understand. For some reason, the program doesn't sort the list completely, for I entered a string beginning with the letter h and one with the letter a and it printed the string starting with "h" before "a".
@GenericUser01 Fixed, I forgot to decrement j in the while loop.
Wow, you are a genius. Looking at that whole while loop just makes me nauseous. How did you know to do all that?
Though I do have some questions. If array indexes start at 0, how come in the InsertionSort method we initialize int i = 1. char tmp[MAX_STRING_LEN]; just creates a string for temporary storage? strncpy(tmp, list[j - 1], sizeof(tmp) - 1); copies the string at the given index into tmp and tmp[sizeof(tmp) - 1] = '\0'; changes the last value in the array to the end char?
How would I do something typing a sentence and the program storing each word seperated by white space? So if I type, "I am learning C but it is not going well." the strings stored in the array would be "I", "am", "learning", "C", "but", etc. I figured that we would have to do an if-statement of some sort that checks to see if the next char is a space and that the input is over if the last char is a period?
|
1

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

Improve this answer

1 Comment

How could this be changed to implement insertion sort? The class name suggests that this is bubble sort, but we are instructed to use insertion sort.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.