[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
?
Solved

IMPLEMENTING NATURAL MERGE FOR LINKED LIST ( NOT FOR FILE )

Posted on 2007-04-10
5
Medium Priority
?
386 Views
Last Modified: 2009-12-16
I need u to help me correct this code of implementing NATURAL MERGE FOR LINKED LIST ( NOT FOR FILE ), I base on the ideas of natural merge on file to do it.

HERE IS MY SOURCE CODE
typedef struct NODE{
      elem data;
        struct NODE *next;
} NODE;

typedef NODE *list;

////////////////// NATURAL SORT FILE USE LINKED LIST //////////////////////

void copyrun2(list &l1, list &l2)
{
      list p2 = l2;

      list pl1 = l1;
      list pl2 = l1->next;

      while(p2->next!=NULL)
      {
              
                p2 = p2->next;
      }

      while(pl2!=NULL && pl2->data >= l1->data)
      {
            l1 = l1->next;
                pl2 = pl2->next;
      }

      p2 = pl1;
        l1->next = NULL;
      l1 = pl2;
}

void distribute2(list &l1, list &l2, list &l3)
{
      do
      {
            copyrun2(l1,l2);
            if(l1!=NULL)
                  copyrun2(l1,l3);
      }
      while(l1!=NULL);
}

void mergerun2(list &l1, list &l2, list &l3)
{
      l1 = new NODE;
      list p2 = l2->next;
      list p4 = l3->next;

      while(l2->data < p2->data && l3->data < p4->data && p2 !=NULL && p4!= NULL)
      {
            if(l2->data < l3->data)
            {
                  l1->next = l2;
                  l2 = l2->next;
                  l1 = l1->next;
                  p2 = p2->next;
            }
            else
            {
                  l1->next = l3;
                  l3 = l3->next;
                  l1 = l1->next;
                  p4 = p4->next;
            }

      }
      while(l2->data < p2->data)
      {
            l1->next = l2;
            l2 = l2->next;
            l1 = l1->next;
            p2 = p2->next;
      }
      while(l3->data < p4->data)
      {
            l1->next = l3;
            l3 = l3->next;
            l1 = l1->next;
            p4 = p4->next;
      }
}

void merge2(list &l1, list &l2, list &l3, int &R)
{
      R=0;
      list p1 = new NODE;
      cout<<"AAAAAAAAAAAAAAAAAAAAAAAAAAAA";
      while(l2!=NULL && l3!=NULL)
      {
            mergerun2(l1,l2,l3);
                R++;
      }
      while(l2!=NULL)
      {
            copyrun2(l2,l1);
            R++;
      }
      while(l3!=NULL)
      {
            copyrun2(l3,l1);
            R++;
      }
      l1 = p1;

}

void natural_list_sort(list &l1)
{
      int R;
      list l2=NULL, l3=NULL;
      do
      {
            distribute2(l1,l2,l3);
            merge2(l1,l2,l3,R);
      }
      while(R>1);
}

IN MAIN FUNCTION u CALL natural_list_sort(list &l1) to run it
0
Comment
Question by:bpc1985
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
5 Comments
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 1000 total points
ID: 18882257
Hi bpc1985,

It looks like you've made this natural sort process a lot harder than it needs to be.   :(

Coding stype can be recursive or iterative.  If you can get your head wrapped around the recursive calls, this generally results in cleaner and shorter code.

The recursive call looks something like this:

call X(root)
within X:
  Find Run1  (length x)
  Find Run2  (length y)
  Merge in place (generating run of length x+y)
  call X (start +(x+y))
  Merge returned string with Run1.

or

call X(root)
within X:
  Find run1  (length x)
  call X (start + x)
  Merge in place (run1 and the run returned by (X)


0
 
LVL 11

Assisted Solution

by:KurtVon
KurtVon earned 1000 total points
ID: 18882283
This looks like homework, so I can only give a few egeneral hints, but it looks like there are a number of typos in it.  For example, in copyrun2 the assignment for pl2 seems to be incorrect.  Don't you want the *next* element to be l1?

It might be a good idea to put a number of cout<< statements in the functions and watching the order things are done carefully.

Hope this helps.
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 18883478

  A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K

The list above represents a linked list of 11 runs.  The runs can be any length.

One possible solution is to identify the first run, then iteratively locate each successive run and merge it into the first.  This is not the ideal solution as if run A were 10,000 items each each subsequent run contained only 1 item, the algorithm could have to scan run the 10,000 items 10 times.  It would work, but be inefficient.

A better solution is to process the list recursively.  Merge the list in pairs, generating AB, CD, EF, GH, IJ, K.  Then merge these in pairs generating ABCD, EFGH, IJK.  Merge again generating ABCDEFGH, IJK.  The final merge generates ABCDEFGHIJK.  By using a recursive process, each call to the function identifies the start and end point of a run.  When the function merges two runs, the starting point of the merged items becomes the starting point of one of the two runs and the end point becomes the ending point of one of the two runs.  After the initial scan, there's no need to hunt around looking for runs.

Draw the 11 items on a piece of paper and connect each of the item pairs with V shaped lines.  Then connect these connections with V shaped lines.  Repeat.  The structure that you've drawn looks like a binary tree.  This is your objective in identifying and processing runs.


Kent
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

650 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question