Insertion sorting strings.

This is a discussion on Insertion sorting strings. within the C Programming forums, part of the General Programming Boards category; My teacher said we have to use the same implementation as on this site Insertion sort - Wikipedia, the free ...

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    117

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

    Last edited by mgracecar; 04-10-2012 at 06:49 PM.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,415
    You can't compare strings that way in C.

    You have to use a function... some sort of function for string comparison.

    Soma

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    117
    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
    Last edited by mgracecar; 04-10-2012 at 07:36 PM.

  4. #4
    Registered User
    Join Date
    Feb 2012
    Posts
    117
    Hmm that's still giving me a segmentation fault. Not sure where my error is exactly.
    It seems to me that this error is happening after 10 lines of strings.

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Shouldn't you just be swapping the pointers? Not strcpy'ing things around (possibly into spaces with not enough memory).
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting Strings
    By code_lover in forum C Programming
    Replies: 3
    Last Post: 10-12-2011, 01:18 AM
  2. Sorting strings
    By yacek in forum C Programming
    Replies: 2
    Last Post: 12-11-2010, 02:07 PM
  3. Sorting Strings
    By Derek5272 in forum C++ Programming
    Replies: 40
    Last Post: 08-24-2003, 11:12 PM
  4. How do i use Insertion for sorting?
    By kenny3b in forum C++ Programming
    Replies: 2
    Last Post: 03-29-2003, 10:48 AM
  5. Sorting by Insertion
    By Bada Bing in forum C Programming
    Replies: 3
    Last Post: 11-17-2001, 11:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21