Insertion sort of strings that exist in an array

Question

In this program, I get an integer number from the user, for example 3, and the user enters 3 strings. Then I should find the longest string, and print it in reverse.

But I think that my insertion sort code has a problem, and I can't find it.

This is the complete code :

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

static void fatal(const char *msg)
{
    fprintf(stderr, "%s\n", msg);
    exit(EXIT_FAILURE);
}

int main(void)
{
    int n;

    printf("How many strings do you want to enter? ");
    if (1 != scanf("%d", &n) || 1 > n || n > 32)
        fatal("Invalid size specified.");

    char strings[n][64];

    for (int i = 0; i < n; i++) {
        printf("Please enter string #%d: ", i + 1);
        if (1 != scanf("%63s", strings[i]))
            fatal("Invalid string input.");
    }
    char selected[100];
    int o;
    int j;
    for (j = 1; j < n; j++)
    {
        strcpy(selected, strings[j]);
        o = j - 1;
        while ((j >= 0) && (strcmp(selected, strings[o]) > 0))
        {
            strcpy(strings[o+1], strings[o]);
            o--;
        }
        strcpy(strings[o + 1], selected);
    }
    puts(strrev(strings[n-1]));
}

Insertion sort part:

char selected[100];
int o;
int j;
for (j = 1; j < n; j++)
{
    strcpy(selected, strings[j]);
    o = j - 1;
    while ((j >= 0) && (strcmp(selected, strings[o]) > 0))
    {
        strcpy(strings[o+1], strings[o]);
        o--;
    }
    strcpy(strings[o + 1], selected);
}

Answer 1

If we modify your code slightly to simply print the strings array after sorting, we can see that not all has gone according to plan.

$ ./a.out
How many strings do you want to enter? 3
Please enter string #1: hello
Please enter string #2: foo
Please enter string #3: wooble
0:
1: hello
2: foo

With some slight modifications, we can properly implement selection sort and get the right order.

We must iterate n-1 times over the array. On each iteration we'll move the shortest element forward, meaning we can consider this sorted. On each iteration an iteration of the remaining array must be performed to find the index of the shortest element.

We can then use a series of calls to strcpy (using char temp[100] as a temp buffer) to swap the strings.

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

static void fatal(const char *msg)
{
    fprintf(stderr, "%s\n", msg);
    exit(EXIT_FAILURE);
}

int main(void)
{
    int n;

    printf("How many strings do you want to enter? ");
    if (1 != scanf("%d", &n) || 1 > n || n > 32)
        fatal("Invalid size specified.");

    char strings[n][64];

    for (int i = 0; i < n; i++) {
        printf("Please enter string #%d: ", i + 1);
        if (1 != scanf("%63s", strings[i]))
            fatal("Invalid string input.");
    }
    
    for (int i = 0; i < n-1; i++)
    {
        int shortest_length = strlen(strings[i]);
        int shortest_len_idx = i;

        for (int j = i+1; j < n; j++) {
            if (strlen(strings[j]) < shortest_length) {
                shortest_len_idx = j;
            }
        }

        char temp[100] = {0};

        strcpy(temp, strings[i]);
        strcpy(strings[i], strings[shortest_len_idx]);
        strcpy(strings[shortest_len_idx], temp);
    }

    for (int i = 0; i < n; i++) printf("%d: %s\n", i, strings[i]);
}

$ ./a.out
How many strings do you want to enter? 3
Please enter string #1: hello
Please enter string #2: foo
Please enter string #3: wooble
0: foo
1: hello
2: wooble

You might also use a struct to "cache" each strings length, preventing repeated calls to strlen.

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

#define MAX_STR_LEN 64

typedef struct {
    int length;
    char str[MAX_STR_LEN];
} string_info;

static void fatal(const char *msg)
{
    fprintf(stderr, "%s\n", msg);
    exit(EXIT_FAILURE);
}

int main(void)
{
    int n;

    printf("How many strings do you want to enter? ");
    if (1 != scanf("%d", &n) || 1 > n || n > 32)
        fatal("Invalid size specified.");

    string_info strings[n];

    for (int i = 0; i < n; i++) {
        printf("Please enter string #%d: ", i + 1);
        char fmt[100] = {0};
        sprintf(fmt, "%%%ds", MAX_STR_LEN-1);
        if (1 != scanf(fmt,  strings[i].str))
            fatal("Invalid string input.");
        strings[i].length = strlen(strings[i].str);
    }

    for (int i = 0; i < n-1; i++)
    {
        int shortest_length = strings[i].length;
        int shortest_len_idx = i;
        for (int j = i+1; j < n; j++) {
            if (strings[j].length < shortest_length) {
                shortest_len_idx = j;
            }
        }

        string_info temp;

        strcpy(temp.str, strings[i].str);
        strcpy(strings[i].str, strings[shortest_len_idx].str);
        strcpy(strings[shortest_len_idx].str, temp.str);

        temp.length = strings[i].length;
        strings[i].length = strings[shortest_len_idx].length;
        strings[shortest_len_idx].length = temp.length;
    }

    for (int i = 0; i < n; i++) printf("%d: %s\n", i, strings[i].str);
}