Порядок строк в массиве

Question

У меня есть следующий код,
, как вы, наверное, ожидали увидеть вывод последней строки: a , b ,c ,d, но фактический вывод:

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

последняя строка, почему я вижу это?

#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

Причина в том, что эта строка str[j] = str_tmp[i]; наименьший элемент, все еще там, где b, вам нужно поменять его местами

Пожалуйста, используйте свопинг с простым подходом

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

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

    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (strcmp(str_tmp[i], str_tmp[j]) < 0)
            {
                temp = str_tmp[i];
                str_tmp[i] = str_tmp[j];
                str_tmp[j] = temp;
            }
        }
    }

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

    return 0;
}

Answer 2

Проблема в том, что этот l oop

    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");
        }
    }

не останавливает свои итерации, когда выполняется условие в операторе if

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

.

Таким образом, когда у вас есть следующие значения в массиве назначения

a c d (null)

, тогда для j, равного 1, условие

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

оценивается как true и в результате вы получаете

a b c d

, но l oop продолжает свои итерации и для j, равного 2, снова условие

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

возвращает true, и в результате элемент str_tmp [i [вставляется в позицию 2 и вы получите

a b b c

Вы должны прервать l oop, как только условие будет выполнено.

Вот ваша обновленная программа.

#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;
}

Ее вывод

d 
a d 
a c d 
a b c d 

Фактически один l oop является избыточным. Также не рекомендуется использовать магические числа c, такие как 4. Программу можно переписать следующим образом:

#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;
}

Поскольку теперь программа не зависит от магических чисел c, число 4 можно добавьте любое количество новых элементов в массив tmp_str, и программа будет работать без каких-либо других изменений. Например, если вы заполняете массив tmp_str инициализаторами следующим образом

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

, тогда вывод программы будет

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 

Вы можете переместить код метода сортировки вставкой в ​​отдельный функция. Например

#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;
}