Thread: Insertion sorting strings.

My teacher said we have to use the same implementation as on this site

Insertion sort - Wikipedia, the free encyclopedia

under the part that says

"Below is the pseudocode for insertion sort for a zero-based array (as in C):"

Anyways I have taken the lines from the file and allocated memory for each string and put them in an array of strings.

Having trouble sorting them using this method though.
Here is my code for that function so far.
I haven't commented it yet, but Max_lines is the total amount of lines in the file. char** words is the array where I'm storing the strings.
It seems I have a problem when trying to use insertion method because I can print these off fine without the function, just not in the correct order.
Thanks in advance for any help

Code:

char **Insertion_sort(char** words, int Max_lines){
 int i, j;
 char *temp;
 
 for( i = 1 ; i < Max_lines; i++)
      {
       temp = words[i];
       j = i-1;
        while ( j >= 0 && words[j]>temp)
          {
                words[j+1]=words[j];
                j=j-1;
          }
        words[j+1] = temp;      
      }    
return words;

}

And here is my entire code so far for any references needed.

Code:

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


char **getWords(int *Max_lines);
char **Insertion_sort(char** words, int Max_lines);
void print_lines(char**words, int Max_lines);

int main()
{
    char **words;
    int Max_lines = 0;

    words = getWords(&Max_lines);
    words = Insertion_sort(words, Max_lines);
    print_lines(words, Max_lines);
    
    while (Max_lines >=0)
          free(words[Max_lines]);
    free(words);
    
getchar();
return 0;
}


char **getWords(int *Max_lines)
{
    FILE *fp;
    char buffer[22];
    char **words, **temp;
    int counter = 0;
    int n = 100;
    
    words = malloc(n * sizeof(char *) );
    printf("Initial array size is 100 words\n");
    
    if ( (fp = fopen("word.txt", "r" )) == NULL )
    {
     printf("Couldn't open file\n");
     exit(1); 
    }
    
    while( fgets(buffer, sizeof(buffer), fp))
    {
           strtok(buffer, "\n");
           words[counter] = malloc(strlen(buffer)+1);
           strcpy(words[counter], buffer);
           
           if ( (counter+1) == n )
           {
              n = n*2;
              temp= realloc(words, n*sizeof(char*));
              if(temp != NULL)
                      words = temp;
              else
              {
                  printf("unable to reallocate\n");
                  exit(1);
              }
              printf("Reached limit...increasing array to %d words\n", n);
           }    
           counter++;
    }        
fclose(fp);
*Max_lines = counter;  
return words;     
}


char **Insertion_sort(char** words, int Max_lines)
{
 int i, j;
 char *temp;
 
 for( i = 1 ; i < Max_lines; i++)
      {
       temp = words[i];
       j = i-1;
        while ( j >= 0 && words[j]>temp)
          {
                words[j+1]=words[j];
                j=j-1;
          }
        words[j+1] = temp;      
      }    
return words;
}


void print_lines(char**words, int Max_lines)
{
     int i;
     printf("\n\n");
     for(i = 0; i < Max_lines; i++)
           printf("%d: %s\n", i ,  words[i]);
}

That's what I thought too.
So I changed it to this...

Code:

char **Insertion_sort(char** words, int Max_lines){
 int i, j;
 char *temp;
 
 for( i = 1 ; i < Max_lines; i++)
      {
       strcpy(temp, words[i]);
       j = i-1;
         while ( j >= 0 && strcmp(words[j], temp)>0)
          {
                strcpy(words[j+1], words[j]);
                j=j-1;
          }
        strcpy(words[j+1],temp);      
      }    
return words;
}

edit* this seems to be working on a little test code. I'll see if it works with more. Thanks

Shouldn't you just be swapping the pointers? Not strcpy'ing things around (possibly into spaces with not enough memory).