Thread: "insert sort with head and tail pointers"

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    4

    Thumbs up "insert sort with head and tail pointers"

    Hi I am trying to make an insertion sort with Linklist.
    I am sorting by the parameter time.
    I think it's semi working but what is the easiest way to implement an insert sort with tail and a head pointer.

    The delink() and addNode()... functions works correctly.
    Insert(....) is the insert sort fcn.

    Thanks for your help.

    Code:
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    struct node {
        int id;
        int time;
        struct node* next;
    };
    /* if it's the first item, pass in HEAD
     * else pass in the TAIL
     */
    void addNode(struct node** head, struct node** tail, int id)
    {
        struct node* new = malloc(sizeof(struct node* ));
        if(*head == NULL)
        {
            new->id = id;
            new->next = NULL;
            *head = new;
            *tail = new;
        }
        else
        {
            new->id = id;
            new->next = NULL;
            (*tail)->next = new;
            *tail = new;
        }
    
    
    }
    void insert(struct node** head, struct node** tail,int id, int time)
    {
        struct node* new = malloc(sizeof(struct node*));
        struct node* start;
        //When adding the first element.
        if(*head == NULL)
        {
            printf("first time\n");
    
            new->id = id;
            new->next = NULL;
            new->time = time;
            *head = new;
            *tail = new;
            printf("first node %d\n", (*head)->id);
        }
        else
        {
        //insert sort
        //find the correct spot to insert the new element
        //
            start = *head;
            while(start->next != NULL &&  (start->next->time <= time))
            {
                printf("current node %d__ time %d\n", (start)->id, start->time  );
                start = start->next;
            }
        
            new->id = id;
            new->time = time;            
            
            // if we have to insert between nodes
            //then use the start pointer, 
            //we place the node after whatever the start pointer points to.
            
            //*****must add node before the first node if the new node has to be the first node
            if(start == *head)
            {
                printf("in First node statement\n");
                new->next = start;
                start = new;
                *head = start;
    
            }
            //new node needs to placed between two nodes
            else
            {
                printf("in Between nodes statement\n");
                new->next = start->next;
                start->next = new;
    
            }
        }
    
    
    }
    void printList(struct node* head)
    {
        
        while(head != NULL)
        {
            printf("ID: %d  Time:> %d\n", head->id, head->time);
            head = head->next;
    
        }
    
    }
    int delink(struct node** head)
    {
        int id = (*head)->id;
        *head = (*head)->next;
    
        return  id;
    }
    int main()
    {
        struct node* head;
        struct node* tail;
        
        head = NULL;
        tail = head;
    
        //int i;
        //int t;
        /*
        for(i = 0; i < 5; i++);
        {
            if(i == 4)
                 t = 1;
            insert(&head,&tail, i, t);
        }*/
        insert(&head, &tail, 2, 4);
        insert(&head, &tail, 5, 3);
        insert(&head, &tail, 3, 1);
        insert(&head, &tail, 1, 5);
        insert(&head, &tail, 4, 2);
        printList(head);
    
        return 0;
    }
    Last edited by noway2; 10-24-2011 at 08:04 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    if head is null or this value < head value
        this->next = head
        head = this
    if this value > tail value
        tail->next = this
        tail = this
    else
        loop through until you find where you want
        prev->next = this
        this->next = current

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    4
    Quote Originally Posted by quzah View Post
    Code:
    if head is null or this value < head value
        this->next = head
        head = this
    if this value > tail value
        tail->next = this
        tail = this
    else
        loop through until you find where you want
        prev->next = this
        this->next = current

    Quzah.
    don't we need to initialized the tail pointer to the first node as well.. not just the head pointer...
    Thanks for your Pseudocode...it helped alot..
    I got it to functioning with minor tweaks..
    Code:
           if(*head == NULL || time < (*head)->time)
            {
                    if(*head == NULL)
                            *tail = new;
                    new->next = *head;
                    *head = new;
            }
            else if (time > (*tail)->time)
            {
                    (*tail)->next = new;
                    *tail = new;
            }
            else
            {
                    start = *head;
                    while((start->next != NULL) && (start->next->time <= time))
                    {
                            start = start->next;
                    }
                    new->next = start->next;
                    start->next = new;
    
    
            }
    Last edited by noway2; 10-24-2011 at 10:47 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 10-21-2011, 01:30 PM
  2. Polymorphism - "pointers" or "references"?
    By Petike in forum C++ Programming
    Replies: 10
    Last Post: 06-04-2009, 05:06 PM
  3. Replies: 2
    Last Post: 10-24-2005, 01:32 PM
  4. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 08:25 AM
  5. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 07:59 AM

Tags for this Thread