Thread: Quick Sort or Merge Sort???

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    85

    Quick Sort or Merge Sort???

    Hello,

    I have a college assignment due TONIGHT!!!!!!! I am having a lot of trouble.... I have been trying by hand on paper and in DevC++ and with pictures...I am very frustrated to say the least. My assignment is to do a mergesort or a Quicksort on a linked list.

    The list is singaly linked and I have to write all of the code for the list...can't ust the ADT's of STL's for list the others like strcmp, etc are ok. I have no ideas left. If there is a willing programmer out there that could help it would be great. I have some code, but I think that itis so garbled that I am not going to post it.

    ALSO I have used these boards before with only about a 10% success rate. Please only help if you are willing to see it through until the end...I am have a problem with getting help from people who guide me into a corner and then simply stop posting.

    To anyone that will help...Thank you already!

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I have a college assignment due TONIGHT!!!!!!!
    Uh huh. That's a common issue.

    >My assignment is to do a mergesort or a Quicksort on a linked list.
    Well, merge sort is well suited to linked lists, so that's not much of a problem. Following that link will give you one hell of a head start. Since you said merge sort or quicksort, I'd suggest you go with merge sort because quicksort takes some thought (even though it's a terribly interesting exercise) while merge sort is pretty self-explanatory for lists. You don't sound like you're looking for a terribly interesting exercise at the moment.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    HERE IS THE CONCEPT THAT I WAS LOOKING AT
    Code:
    struct bucket_struct{
           node* head;
           node* tail;
    };
    
    
    mergesort (start,stop)
        if (start->nxt != NULL)
        {
               mid = findmid(start,stop);
               mergesort(start,mid)
               mergesort(mid->nxt,stop)
               merge(start,mid,stop)
         }
    
    
    merge(start,mid,stop)
    bucket_struct newList;
    newList.head=NULL
    newList.tail=NULL
    node *l1 = start
    node* l2 = mid->nxt;
    mid->nxt = NULL;
    
    while(l1 != NULL && l2 != NULL)
    {
        if(l1->field <= l2->field)
        {
             if(newList = NULL)
             {
                 newList.head = l1
             }
             newList.tail->nxt = l1
             l1 = l1->nxt
         }
         else
             if(newList = NULL)
             {
                 newList.head = l2
             }
             newList.tail->nxt = l2
             l2 = l2->nxt
          }
    }
    start_ptr = newList.head
    I DUNNO THOUGH?

  4. #4
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    Here is my compiling code thus far
    Code:
    void mergesort(node *start,node *stop)
    {
        node * mid;
        if (start->nxt != NULL)
        {
               mid = find_mid(start,stop);
               mergesort(start,mid);
               mergesort(mid->nxt,stop);
               merge(start,mid,stop);
         }
    
    }
    void merge(node *start,node *mid,node *stop)
    {
    bucket_struct newList;
    newList.head=NULL;
    newList.tail=NULL;
    node *l1 = start;
    node* l2 = mid->nxt;
    mid->nxt = NULL;
    
    while(l1 != NULL && l2 != NULL)
    {
        if(l1->node_struct.d_name <= l2->node_struct.d_name)
        {
             if(newList.head= NULL)
             {
                 newList.head = l1;
             }
             newList.tail->nxt = l1;
             l1 = l1->nxt;
         }
         else
         {
             if(newList.head = NULL)
             {
                 newList.head = l2;
             }
             newList.tail->nxt = l2;
             l2 = l2->nxt;
          }
    }
    start_ptr = newList.head;
    }
    
    node *find_mid(node *start, node *stop)
    {
    }

  5. #5
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    Here is my updated find_mid function
    Code:
    node *find_mid(node *start, node *stop)
    {
         int i = 0;
         node * stepper;
         int j;
         
         while(stepper != stop)
         {
                       stepper = stepper->nxt;
                       i++;
         }
         stepper = start;
         for(j = i; j > 0; j--)
         {
               stepper = stepper->nxt;
         }
         return stepper;                   
    }

  6. #6
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    Before the while I added stepper = start; in the find mid......Now an infinate loop in the merge sort

  7. #7
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    I found that the loop is because of the terminating case in the mergesort function....I don't know what to use!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  3. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  4. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM
  5. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM