Strings order in Array

Question

I have the next code,
as you guess I expected to see output last line: a , b ,c ,d but the actual output is:

a d (null) (null)  
a c d (null)  
a b c d  
a b b c

the last line, why I see it?

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

int main ()
{
    char *str_tmp[4] = {"d", "a", "c", "b"};
    char **str = calloc(4, sizeof(char *));

    str[0] = str_tmp[0];

    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (strcmp(str_tmp[i], str[j]) < 0)
            {
                for (int k = i; k > j; k--)
                {
                    str[k] = str[k-1];
                }

                str[j] = str_tmp[i];

                for (int n = 0; n < 4; n++)
                {
                    printf("%s ", str[n]);
                }
                printf("\n");
            }
        }
    }

    return 0;
}

Answer 1

The problem is that this loop

    for (int j = 0; j < i; j++)
    {
        if (strcmp(str_tmp[i], str[j]) < 0)
        {
            for (int k = i; k > j; k--)
            {
                str[k] = str[k-1];
            }

            str[j] = str_tmp[i];

            for (int n = 0; n < 4; n++)
            {
                printf("%s ", str[n]);
            }
            printf("\n");
        }
    }

does not stop its iterations when the condition in the if statement

        if (strcmp(str_tmp[i], str[j]) < 0)

is satisfied.

So when you have the following values in the destination array

a c d (null)

then for j equal to 1 the condition

strcmp(str_tmp[i], str[j]) < 0

evaluates to true and as result you get

a b c d

but the loop continues its iterations and for j equal to 2 again the condition

strcmp(str_tmp[i], str[j]) < 0

yields true and as result the element str_tmp[i[ is inserted in the position 2 and you get

a b b c

You have to interrupt the loop as soon as the condition is satisfied.

Here is your updated program.

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

int main(void) 
{
    char *str_tmp[4] = {"d", "a", "c", "b"};
    char **str = calloc(4, sizeof(char *));

    str[0] = str_tmp[0];

    for (int i = 0; i < 4; i++)
    {
        int j = 0;
        while ( j < i && !( strcmp(str_tmp[i], str[j]) < 0 ) ) j++;
        for (int k = i; k > j; k--)
        {
             str[k] = str[k-1];
        }

        str[j] = str_tmp[i];

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

    free( str );

    return 0;
}

Its output is

d 
a d 
a c d 
a b c d 

In fact one loop is redundant. Also it is a bad idea to use magic numbers like 4. The program can be rewritten the following way

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

int main(void) 
{
    char *str_tmp[] = { "d", "a", "c", "b" };
    const size_t N = sizeof( str_tmp ) / sizeof( *str_tmp );
    char **str = calloc( N, sizeof( char * ) );

    for ( size_t i = 0; i < N; i++ )
    {
        size_t j = i;

        for ( ; j != 0 && strcmp( str_tmp[i], str[j-1] ) < 0; j-- )
        {
             str[j] = str[j-1];
        }

        str[j] = str_tmp[i];

        for ( size_t n = 0; n < i + 1; n++ )
        {
             printf( "%s ", str[n] );
        }

        putchar( '\n' );
    }

    free( str );

    return 0;
}

As now the program does not depend on the magic number 4 you can add any number of new elements to the array tmp_str and the program will work without any other changes. For example if you fill the array tmp_str with initializers the following way

 char *str_tmp[] = { "d", "a", "c", "b", "k", "j", "z", "t" };

then the program output will be

d 
a d 
a c d 
a b c d 
a b c d k 
a b c d j k 
a b c d j k z 
a b c d j k t z 

You could move the code of the insertion sort method in a separate function. For example

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

void insertion_sort( char * s[], size_t n )
{
    for ( size_t i = 1; i < n; i++ )
    {
        if ( strcmp( s[i], s[i-1] )  < 0 )
        {
            char *item = s[i];

            size_t j = i;

            do
            {
                s[j] = s[j-1];
            } while ( --j != 0 && strcmp( item, s[j-1] ) < 0 );

            s[j] = item;
        }           
    }
}

int main(void) 
{
    char *s[] = { "d", "a", "c", "b", "k", "j", "z", "t" };
    const size_t N = sizeof( s ) / sizeof( *s );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%s ", s[i] );
    }

    putchar( '\n' );

    insertion_sort( s, N );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%s ", s[i] );
    }

    putchar( '\n' );

    return 0;
}