Thread: Trouble using Insertion Sort on Double Linked List

  1. #1
    Registered User
    Join Date
    Feb 2014
    Posts
    10

    Trouble using Insertion Sort on Double Linked List

    I am working on an insertion sort that takes the nodes from one list and places them, sorted, into a new list. The problems seem to be coming into play in my For loop initialization, and the final list is never actually sorted correctly. When I try to pass the sortedlist to my print function, valgrind is showing an 'Invalid read of size 8'. Any help on making sure every node is being passed through and sorted correctly would be greatly appreciated.

    1stTry-DLL.c

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct DLNode Node;
    
    typedef struct DLNode
    {
        int ID;
        char *Fname;
        char *Lname;
        char *Dept;
        float GPA;
        Node * prev;
        Node * next;
    } Node;
    
    typedef struct DLList
    {
        int count;
        Node * first;
        Node * last;
    } List;
    
    void DLList_init(List * list)
    {
        list->first = NULL;
        list->last = NULL;
        list->count = 0;
    }
    
    void DLList_add_node(List * list, int ID, char *Fname, char *Lname, char *Dept, float GPA)
    {
        Node * newNode;
    
        newNode = malloc(sizeof(Node));
        if(!newNode)
        {
            printf("Malloc failed, new node not created.");
            exit(EXIT_FAILURE);
        }
    
        newNode->ID = ID;
        newNode->Fname = Fname;
        newNode->Lname = Lname;
        newNode->Dept = Dept;
        newNode->GPA = GPA;
    
        if(list->last)
        {
            list->last->next = newNode;
            newNode->prev = list->last;
            list->last = newNode;
        } else {
            list->first = newNode;
            list->last = newNode;
        }
        
        list->count++;
    }
    
    void DLList_print(List * sortedlist, FILE *fout)
    {
        Node * node;
    
        for(node = sortedlist->first; node != NULL; node = node->next)
        {
            fprintf(fout, "%d,%s,%s,%s,%f\n", node->ID, node->Fname, node->Lname, node->Dept, node->GPA);
            free(node->Dept);
            free(node->Lname);
            free(node->Fname);
            free(node);
        }
    }
    
    void Insertion_sort(List * list, List * sortedlist, FILE *fout)
    {
        Node * indexNode;
        Node * nextNode;
        Node * firstNode;
    
        indexNode = list->first;
        nextNode = indexNode->next;
    
        for(indexNode = list->first; indexNode->next != NULL; indexNode = indexNode->next)
        {
            nextNode = indexNode->next;
    
            if(indexNode->ID < nextNode->ID)
            {
                if(sortedlist->first == NULL)
                {
                    firstNode = indexNode;
                    sortedlist->first = firstNode;
                    sortedlist->last = firstNode;
                } else {
                    firstNode->next = indexNode;
                    indexNode->prev = firstNode;
                    sortedlist->last = indexNode;
                }
                
            } else {
                nextNode->prev = indexNode;
                indexNode->next = nextNode;
                sortedlist->last = nextNode;
            } 
            
        }
        
        DLList_print(sortedlist, fout);
    }
    
    int main(int argc, char *argv[])
    {
        FILE *fin, *fout;
        int ID;
        char *Fname;
        char *Lname;
        char *Dept;
        float GPA;
        char *fin_path;
        char *fout_path;
    
        List sortedlist;
        DLList_init(& sortedlist);
        
        List list;        //Create list
        DLList_init(& list);    //and initialize NULL pointers
    
        if(argv[1] && argv[2])
        {
            fin_path = argv[1];
            fout_path = argv[2];
        } else {
            printf("Input and output file names were not supplied!\n");
            return 1;
        }
    
        fin = fopen(fin_path, "r");
        if(fin == NULL)
        {
            printf("Can't open input file!\n");
            return 1;
        }
    
        while (fscanf(fin, "%d %ms %ms %ms %f", &ID, &Fname, &Lname, &Dept, &GPA) == 5)
        {
            DLList_add_node(& list, ID, Fname, Lname, Dept, GPA);
        }
    
        fout = fopen(fout_path, "w");
        if(fout == NULL)
        {
            printf("Can't open output file!");
            return 1;
        }
    
        Insertion_sort(& list, & sortedlist, fout);
    
        //DLList_print(& list, fout);
    
        fclose(fin);
        fclose(fout);
    
        return 0;
    }
    Last edited by mattdol; 02-04-2014 at 02:52 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Code goes in [code][/code] tags. Please edit your post to fix this. Also, make sure the code is properly indented (see here). This allows us to easily read the code, and help you find/fix your problems.

  3. #3
    Registered User
    Join Date
    Feb 2014
    Posts
    10
    Sorry about that, this is my first time posting a question here. Thanks for the formatting tip.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Much better. A few more things:

    Compile your code at maximum warning level:
    Code:
    $ make foo
    gcc -Wall -ggdb3 -pedantic -std=c99 -O0 -o foo foo.c -lm -lpthread -lrt
    foo.c:15:3: warning: redefinition of typedef ‘Node’ [-pedantic]
    foo.c:4:23: note: previous declaration of ‘Node’ was here
    foo.c: In function ‘main’:
    foo.c:145:5: warning: ISO C does not support the 'm' scanf flag [-Wformat]
    foo.c:145:5: warning: ISO C does not support the 'm' scanf flag [-Wformat]
    foo.c:145:5: warning: ISO C does not support the 'm' scanf flag [-Wformat]
    You don't need the typedef on the struct if you put a separate one above it. Also, the m flag is non-standard, but it may be okay if you know that whoever grades your code will be using GNU extensions, and accepts the m flag. Else, use char arrays, and malloc your own memory if need be.

    Also, providing the input file that demonstrates the problem would be helpful. And describing the problem a little more would help. What is the exact nature of the sorting: by ID number, by first name, last name then first, GPA, etc. What if two people have the same ID/name/GPA/department?

  5. #5
    Registered User
    Join Date
    Feb 2014
    Posts
    10
    The m flag is to be included as part of the assignment, so that the character buffers can be variable length.
    The input file is formatted as:
    StudentID Firstname Lastname Department GPA with any amount of whitespace

    And the output file is to be formatted as:
    StudentID,Firstname,Lastname,Department,GPA with only commas separating the elements.

    StudentID is a 7 digit integer, GPA is a float between 0 and 4, the rest are character strings.
    The sorting is done exclusively on the StudentID number, and no two StudentID numbers will be the same.

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Code:
        char *Fname;
        char *Lname;
        char *Dept;
    Where do you allocate space for the names?

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    A function should do one thing and do it well. DLList_print should not free anything. That keeps you from reusing it elsewhere. For example, I tried to print list and sortedlist each time through the sorting loop, but it freed everything and broke it. Make a separate DLList_free() function that frees all the nodes and their contents. This will be helpful in debugging, as you see below. This is the print code I added around line 85:
    Code:
            printf("Iteration %d\n", i++);
            printf("List:\n");
            DLList_print(list, stdout);
            printf("Sorted List:\n");
            DLList_print(sortedlist, stdout);
            printf("\n");
    Note, DLList_print had the all the free()s removed. Here is the input file and sample run
    Code:
    $ cat in.txt 
    2 bbb BBB Bdept 2.34
    4 ddd DDD Ddept 4.56
    1 aaa AAA Adept 1.23
    5 eee EEE Edept 5.67
    3 ccc CCC Cdept 3.45
    
    
    $ ./foo in.txt out.txt
    $ ./foo in.txt out.txt 
    Iteration 0
    List:
    2,bbb,BBB,Bdept,2.340000
    4,ddd,DDD,Ddept,4.560000
    1,aaa,AAA,Adept,1.230000
    5,eee,EEE,Edept,5.670000
    3,ccc,CCC,Cdept,3.450000
    Sorted List:
    
    
    Iteration 1
    List:
    2,bbb,BBB,Bdept,2.340000
    4,ddd,DDD,Ddept,4.560000
    1,aaa,AAA,Adept,1.230000
    5,eee,EEE,Edept,5.670000
    3,ccc,CCC,Cdept,3.450000
    Sorted List:
    2,bbb,BBB,Bdept,2.340000
    4,ddd,DDD,Ddept,4.560000
    1,aaa,AAA,Adept,1.230000
    5,eee,EEE,Edept,5.670000
    3,ccc,CCC,Cdept,3.450000
    
    
    Iteration 2
    List:
    2,bbb,BBB,Bdept,2.340000
    4,ddd,DDD,Ddept,4.560000
    1,aaa,AAA,Adept,1.230000
    5,eee,EEE,Edept,5.670000
    3,ccc,CCC,Cdept,3.450000
    Sorted List:
    2,bbb,BBB,Bdept,2.340000
    4,ddd,DDD,Ddept,4.560000
    1,aaa,AAA,Adept,1.230000
    5,eee,EEE,Edept,5.670000
    3,ccc,CCC,Cdept,3.450000
    
    
    Iteration 3
    List:
    2,bbb,BBB,Bdept,2.340000
    1,aaa,AAA,Adept,1.230000
    5,eee,EEE,Edept,5.670000
    3,ccc,CCC,Cdept,3.450000
    Sorted List:
    2,bbb,BBB,Bdept,2.340000
    1,aaa,AAA,Adept,1.230000
    5,eee,EEE,Edept,5.670000
    3,ccc,CCC,Cdept,3.450000
    Notice that, after the first iteration through the loop, sortedlist already "has 5 elements". You probably either need to sort the list in place (i.e. only use list, not sortedlist), or make a complete copy of each node as you insert into sortedlist.

    Also, lines 81 and 82 are redundant given lines 84 and 85.
    Last edited by anduril462; 02-04-2014 at 03:33 PM. Reason: Fixed typo and old version of debug output

  8. #8
    Registered User
    Join Date
    Feb 2014
    Posts
    10
    Tim,
    space does not need to be allocated for those names due to the m flag being used with fscanf. This was given as part of the assignment.

    Anduril,
    Thanks for the help with the print function. I am in the process writing a new function that will recursively move through my list and sort my nodes with the help of a temp node, so that I won't need to use the second list.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    I don't think you need recursion, though it is possible that way. Fix your print function to just print and your sort function to just sort (i.e. remove the print to fout from it). Add the DLList_free as I suggested.

    Then, add 2 more functions. One that removes a pointed-to node from the list, and another that inserts a node before a pointed-to node in a list. Something like:
    Code:
    Node *DLList_remove_node(List *list, Node *node)
    {
        // look for node in list
        // if not found
        //     return NULL
        // remove node from list
        // update list->first and/or list->last as appropriate, and update the prev/next pointers of the neighbors of node
        // return node
    }
    
    void DLList_insert_before(List *list, Node *insert_before_this_node, Node *node_to_insert)
    {
        // search list for insert_before_this_node
        // if not found
        //     return
        // insert node_to_insert before the specified node
        // update list->first and/or list->last as appropriate
        // update prev/next pointers of neighbors of insert_before_this_node and update prev/next of node_to_insert
    }
    That should be all you need to implement the classic insertion sort, on the original list, if you understand the algorithm.

    EDIT: You could also do this if you used an "insert after" approach.

  10. #10
    Registered User
    Join Date
    Feb 2014
    Posts
    10
    I have done some modification including breaking print and free into separate functions. I have also tried to make a new sort routine, that calls on a sort loop. I am getting an 'invalid read of size 4' from my Insertion_loop call on line 114 as well as a segmentation fault. Could you take a look at the new Insertion_sort and Insertion_loop functions and identify any problems?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct DLNode Node;
    
    typedef struct DLNode
    {
        int ID;
        char *Fname;
        char *Lname;
        char *Dept;
        float GPA;
        Node * prev;
        Node * next;
    } Node;
    
    typedef struct DLList
    {
        Node * first;
        Node * last;
    } List;
    
    void DLList_init(List * list)
    {
        list->first = NULL;
        list->last = NULL;
    }
    
    void DLList_add_node(List * list, int ID, char *Fname, char *Lname, char *Dept, float GPA)
    {
        Node * newNode;
    
        newNode = malloc(sizeof(Node));
        if(!newNode)
        {
            printf("Malloc failed, new node not created.");
            exit(EXIT_FAILURE);
        }
    
        newNode->ID = ID;
        newNode->Fname = Fname;
        newNode->Lname = Lname;
        newNode->Dept = Dept;
        newNode->GPA = GPA;
    
        if(list->last)
        {
            list->last->next = newNode;
            newNode->prev = list->last;
            list->last = newNode;
        } else {
            list->first = newNode;
            list->last = newNode;
        }
    }
    
    void DLList_print(List * list, FILE *fout)
    {
        Node * node;
    
        for(node = list->first; node != NULL; node = node->next)
        {
            fprintf(fout, "%d,%s,%s,%s,%f\n", node->ID, node->Fname, node->Lname, node->Dept, node->GPA);
            //printf("%d,%s,%s,%s,%f\n", node->ID, node->Fname, node->Lname, node->Dept, node->GPA);
        }
    }
    
    void DLList_free(List * list)
    {
        Node * node;
    
        for(node = list->first; node != NULL; node = node->next)
        {
            free(node->Dept);
            free(node->Lname);
            free(node->Fname);
            free(node);
        }
    
    }
    
    void Insertion_loop(List * list, Node * node1, Node * node2)
    {
        Node * tmpNode;
    
        //printf("Insertion Loop: %d\t%d\n", node1->ID, node2->ID);
    
        if(node1->ID < node2->ID)
        {
            node1 = node2;
            node2 = node2->next;
    
            if(node1 != list->last)
            {
                Insertion_loop(list, node1, node2);
            }
        }
        else
        {
            node2->prev = node1->prev; //swap node2 and node1 locations in the list
            node1->next = node2->next;
            node1->prev = node2;
            node2->next = node1;
    
            if(node2 != list->first)
            {
                node1 = node2->prev; //make node1 the node before node2 
            } else {
                tmpNode = node2; //or swap the names of node1 and node2
                node2 = node1;   // if node2 is currently list->first
                node1 = tmpNode;
            }
            
            Insertion_loop(list, node1, node2);
        }
    }
    
    void Insertion_sort(List * list)
    {
        Node * node1;
        Node * node2; 
    
        node1 = list->first;
        node2 = node1->next;
        
        Insertion_loop(list, node1, node2);
    }
    
    int main(int argc, char *argv[])
    {
        FILE *fin, *fout;
        int ID;
        char *Fname;
        char *Lname;
        char *Dept;
        float GPA;
        char *fin_path;
        char *fout_path;
        
        List list;        //Create list
        DLList_init(& list);    //and initialize NULL pointers
    
        if(argv[1] && argv[2])
        {
            fin_path = argv[1];
            fout_path = argv[2];
        } else {
            printf("Input and output file names were not supplied!\n");
            return 1;
        }
    
        fin = fopen(fin_path, "r");
        if(fin == NULL)
        {
            printf("Can't open input file!\n");
            return 1;
        }
    
        while (fscanf(fin, "%d %ms %ms %ms %f", &ID, &Fname, &Lname, &Dept, &GPA) == 5)
        {
            DLList_add_node(& list, ID, Fname, Lname, Dept, GPA);
        }
    
        fout = fopen(fout_path, "w");
        if(fout == NULL)
        {
            printf("Can't open output file!");
            return 1;
        }
    
        Insertion_sort(& list);
        DLList_print(& list, fout);
        DLList_free(& list);
    
        fclose(fin);
        fclose(fout);
    
        return 0;
    }

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Your new print function is good, but you don't need the commented print line. If you want to print to the screen instead of a file, just pass stdout as the FILE *. It's a built-in handle to the standard output device (typically your screen).

    Your free function is really close. But, once you free(node), all of it's members are invalid, so node = node->next in your loop is invalid. You need one more Node *, say 'temp'. Then your loop body becomes:
    Code:
    temp = node->next;
    free everything
    node = temp;
    I would not bother splitting the sort into multiple functions the way you did*, though you could make it work that way. It's just that the sort logic is not complex enough to really warrant this.

    Take a look at the Wikipedia article on insertion sort (link). Read up and pay close attention to the little graphic example on the right. Notice how it removes a node from the list, then walks backwards looking for where to insert it (note, it may have to go back more than one position to find the right spot to insert). That is exactly the logic you will need in your sort function.

    Another minor note, more a matter of good design than anything: don't open/allocate any resource (e.g. file, memory) earlier than you need to, and close/free/release it as soon as you're no longer need it. Thus, your main would be more like:
    Code:
    fin = fopen
    while (fscanf)
    fclose(fin)
    sort
    fout = fopen
    print to fout
    fclose(fout)
    free list
    For this smallish program, it's not such an issue, but as your programs become more complex, resource management could become an issue. Better to get in good habits early.

    EDIT: I know I'm giving more criticism than compliments, but all in all this is a pretty well-written program, so be proud of it. Plus, you seem to have good planning and organizational skills, which are far more crucial to being a good programmer than most people realize.

    * There is a case for splitting some of the insertion sort code up into multiple functions, but it would involve pulling out the node comparison logic. It would use a function pointers for comparison functions, passing such a function pointer to the sort function, so that you could reuse the same insertion sort function with multiple comparison functions, i.e. same sort function can easily sort by ID, name, GPA, department, etc. This is the same idea the standard C function qsort() uses to generically sort arrays of anything.
    Last edited by anduril462; 02-04-2014 at 06:31 PM.

  12. #12
    Registered User
    Join Date
    Feb 2014
    Posts
    10
    Does this look like something on the right track? It doesn't work yet, but I've already spent a lot of time pursuing dead ends and you seem to know what you're talking about. I can't figure out how to iterate through my list.

    Code:
    void Insertion_sort(List * list)
    {
        Node * index;
        Node * prevNode;
        Node * nextNode;
    
        prevNode = list->first;
        index = prevNode->next;
        nextNode = index->next;
    
        for(index; index != NULL; index = index->next)
        {
            for(index; index != NULL; index = index->prev)
            {
                if(index->ID < prevNode->ID)
                {
                    prevNode->next = nextNode;
                    nextNode->prev = prevNode;
    
                    index->next = prevNode;
                    index->prev = prevNode->prev;
                    prevNode->prev = index;
                }
            }
        }
    }

  13. #13
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    No, that's not really it. Don't start writing code until you have a thorough understanding of the algorithm. After all, if you don't know how to do it, how can you program a computer to do it? Try using a deck of cards, or scraps of paper with number on them, to work through the algorithm so you can see where you would remove a node, where you would insert it. From there, work on an English description, then turn that English into code.

    Once you think you understand the process, post your English/pseudo code here, and I will clear up any issues you have.

  14. #14
    Registered User
    Join Date
    Feb 2014
    Posts
    10
    Here's what I have in English:
    Start with Node 2, call it index (it's pointless to remove the first node and place it back where it is).
    Comparison: If index->ID is less than index->prev->ID, compare with index->prev->prev etc. (This is the part I can't figure out how to code)
    Once index->ID is greater than some other node->ID, place index after that node by removing it from its former location and sewing up the holes, and placing it in the new location by changing the prev and next pointers.
    Repeat for every node (This is the other part I don't know how to code).

    I understand the concept of removing the node and reassigning all of the pointers to put it in the correct location, but not how I can iterate through the nodes to achieve this.

  15. #15
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Iterating would just require another temporary pointer, and a loop with a comparison, so you know when to stop searching backwards for where to insert.

    You definitely seem to have exactly the right idea, but you're pseudo code seems to be doing it a bit backwards. I'll start with the main loop, which you had correct at one point*. Also, note, index is node 1 here, and we'll compare against index->next:
    Code:
    for (index = list->first; index != NULL; index = index->next)
    Now, if they are out of order, you need to walk index->next backwards through the list, until you find it's proper spot
    Code:
    for (index = list->first; index != NULL && index->next != NULL; index = index->next){
        if (index->ID > index->next->ID) {
            node = remove(list, index->next)  // removes index->next and return it
            temp = index;
            while temp is larger than node, and temp has not reached the beginning of the list
                make temp point to the node before the one it points to now
            // now, temp should point adjacent to where you want to insert node
            insert node into list next to temp
    Does that make sense?

    * Note, I think you had a tiny bug, in that you went to the last node, instead of next to last node. Since we look at index->Id and index->next->ID, we must make sure that both index and index->next are not NULL before we try to dereference them to find the IDs. That is the purpose of the && index->next != NULL in my for loop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insertion Sort with Linked Lists
    By Linell Bonnette in forum C++ Programming
    Replies: 1
    Last Post: 11-21-2011, 11:46 PM
  2. Insertion Sort and Linked List
    By dlwlsdn in forum C Programming
    Replies: 2
    Last Post: 01-25-2010, 11:25 PM
  3. Help with Insertion sort on a single linked list
    By goron350 in forum C++ Programming
    Replies: 4
    Last Post: 07-11-2005, 08:38 PM
  4. Linked List Insertion Sort
    By The Brain in forum C++ Programming
    Replies: 4
    Last Post: 04-04-2005, 07:20 PM
  5. Sort strings in double linked list. (Optimize code)
    By netstar in forum C++ Programming
    Replies: 15
    Last Post: 02-28-2005, 01:40 AM

Tags for this Thread