Insert Sort with Strings in C [closed]

Question

I'm trying to make a insert sort with strings. That's my code below.

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

#define MAXLINES 5
#define MAXLINEC 1000

int
main(void)
{
    char lines[MAXLINES][MAXLINEC] = {
        "abcd",
        "fghijk",
        "lmn",
        "opqr",
        "stuvwxyz",
    };
    int i, j;
    char temp[MAXLINEC];

    for (i=0; i<MAXLINES; ++i)
    {
        j = i - 1;
        while (j>=0 && strlen(lines[j]) > strlen (lines[i]))
        {
            strcpy(temp, lines[i]);
            strcpy(lines[i], lines[j]);
            strcpy(lines[j], temp);

            j = j - 1;
        }
    }

    for (i = 0; i<MAXLINES; ++i)
        printf("%s\n", lines[i]);
    return 0;
}

It compiles, the output is correct, but the first element isn't in ordering. It was compiled with "cc -Wall -o main main.c" enter image description here

Answer 1

An insertion sort works by dividing an array into two parts: sorted and unsorted.

A   C   Q | B   X   Z   D   Y
sorted      unsorted

The outer loop can be thought of as “the number of sorted elements”. When the algorithm first starts, the number of sorted elements is zero.

^{⟶ This also aligns with the way array indexing works in C: the first element of the array is at index 0, the second at index 1, etc. So if you have 5 sorted elements, the first unsorted element is at index 5. Nice!}

The next thing an insertion sort does is move the next unsorted element into its sorted position. For integer types, this is typically done as a “swap until sorted” operation, since this nicely localizes accesses.

This is the inner loop. It should be written as starting at the first unsorted element and terminating at no less than one. The comparison should check the element at the current index against the element at current index - 1:

  // outer loop counts number of elements sorted
  // done when all elements are sorted
  for (int i = 0;  i < num_elements;  i++)
  {
    // inner loop
    // done when next element to be sorted either:
    //   is at index 0
    //   tests as sorted in its final position
    for (int j = i;  j > 0;  j--)
    {
      if (a[j-1] < a[j])    // if sorted, then we are done!
        break;
      swap( a[j-1], a[j] ); // otherwise swap closer to sorted and continue
    }
  }

Continuing with our example above, that would be

A   C   Q | B   X   Z   D   Y
            j=i

A   C   B   Q   X   Z   D   Y
        j   i

A   B   C   Q   X   Z   D   Y
    j       i

A   B   C   Q | X   Z   D   Y
                i

Notably, insertion sort is only efficient on short arrays of integer to begin with, but for an array of strings, “swap until sorted” is about the same as deliberately bombing the behavior of your function. Forced to work on such an array directly I would personally just find the insertion point, then do a copy to temp, shift, and copy to destination.

That said, you can totally ignore that and continue as you were. My advice is to:

1. Writa a swap() function to swap two integers.
2. Write a functioning insertion sort over an array of int.
3. Write a swap() function to swap two strings in your array.
4. Modify the insertion sort to work over your array of char[].

The function should not actually change more than it takes to change the data types being sorted!

Answer 2

In this while loop

    while (j>0 && strlen(lines[j]) > strlen (lines[i]))
    {
        strcpy(temp, lines[i]);
        strcpy(lines[i], lines[j]);
        strcpy(lines[j], temp);

        j = j - 1;
    }

the element of the array with index equal to 0 is never processed.

And in the outer for loop

for (i=2; i<MAXLINES; ++i)

you skipped to check the element of the array with index equal to 1.

Answer 3

Remy Lebeau tiene razon, ya que al colocar "for (i=2; i<MAXLINES; ++i)" y luego restarle solo 1 no estas teniendo en cuenta la posición inicial que es 0, y creería que debes también, dentro del bucle While colocar "j >= 0"

In English: Remy Lebeau is right, since by placing "for (i=2; i<MAXLINES; ++i)" and then subtracting only 1 you are not taking into account the initial position which is 0, and I think you should also, within the While loop, place "j >= 0"