Merge Sort on linked list..my code is almost done..please help me onit

C

c

I have worked on this code hours, and get it to work finally on Linux
Debian..
its basically sort a linked list --bubble sort. Also I added a piece
of code to the main function to measure the execution time of the
bubble sort function

what I am trying now is to get a merge sort from another source code
and have it to work on mine and measure the time of execution too


here is my code --

#include <iostream>
#include <time.h>

using namespace std;
class node
{
friend class linklist;
int value;
node *next;

};

class linklist
{
private:
node *first;
node *last;
public:
linklist(){ first = NULL; }
~linklist(){};
void addnode();
void BubbleSort();
//void MergeSort();
void displaynode();

};

void linklist :: addnode()
{
node *newno;
do
{
newno = new node;
newno->next=NULL;
//cout<<"Number : ";
cin>>newno->value;
if(first==NULL)
first=last=newno;
else
{
last->next=newno;
last=newno;
}
}while(newno->value != 0);
}

void linklist :: displaynode()
{
//cout<<"---------------------\nSorted values :\n";
node *curno=first;
while(curno)
{
cout<<curno->value<<'\n';
curno=curno->next;
}
}

void linklist ::BubbleSort()
{
int x,y,m,n=0,put;
node *q, *p, *t;
for(node*q = first ; q ; q=q->next) //balad shodid;
++n;

for(x=1 , t = first ; x<=n-1 ; t = t->next , ++x)
for( y=0 , p = first ; y<n-x ; p = p->next , ++y)
if(p->value > (p->next)->value)
{
put = p->value;
p->value = (p->next)->value;
(p->next)->value = put;
}
}

/*
void linklist ::MergeSort()
{

// your help here please
// your help here please
// your help here please
// your help here please
}
*/

int main()
{
linklist sl;
sl.addnode();
// measure excution time
// stolen from http://bytes.com/topic/c/answers/576635-there-timer-function-c
time_t start_time= clock(); //set the clock
sl.BubbleSort();
float time1 = (float) (clock() - start_time) /CLOCKS_PER_SEC; //
calculate excution time
sl.displaynode();
printf("Bubble-sorting took %f seconds to finish\n", time1);

return 0;
}

---- end of code


and here is the merge sort code from another program..I just want to
get the merge function in this code to work on mine..my code is the
first one ..the one above

--merge sort -- code--------
#include <iostream>
using namespace std;

#define NULL 0

class LinkList
{
private:
struct Node
{
Node* prev;
int value;
Node *next;
};
Node *first;

public :

LinkList()
{
Node *t1 = new Node();
t1->prev = NULL;
t1->value = 4;
t1->next = NULL;
first = t1;

Node *t2 = new Node();
t2->prev = t1;
t2->value = 6;
t2->next = NULL;
t1->next = t2;

Node *t3 = new Node();
t3->prev = t2;
t3->value = 1;
t3->next = NULL;
t2->next = t3;

Node *t4 = new Node();
t4->prev = t3;
t4->value = 5;
t4->next = NULL;
t3->next = t4;

Node *t5 = new Node();
t5->prev = t4;
t5->value = 8;
t5->next = NULL;
t4->next = t5;

Node *t6 = new Node();
t6->prev = t5;
t6->value = 1;
t6->next = NULL;
t5->next = t6;

Node *t7 = new Node();
t7->prev = t6;
t7->value = 0;
t7->next = NULL;
t6->next = t7;
}

~LinkList()
{
Node *temp = first, *current = first;
while(current != NULL)
{
temp = current->next;
delete current;
current = temp;
}

}

void Display()
{
Node *temp;
for(temp = first; temp != NULL; temp = temp->next)
{
cout<<temp->value<<" , ";
}
cout<<endl;
}


void Sort()
{
Node *current, *cur;

for(current = first; current->next != NULL; current = current-
{
Node *minimum = current;
for(cur = current ; cur != NULL; cur = cur->next)
{
if(minimum->value > cur->value)
{
minimum = cur;
}
}
if(minimum != current)
{
Node *current_previous, *current_next, *min_previous,
*min_next;

// Initialize them
current_next = current->next;
min_previous = minimum->prev;
min_next = minimum->next;
current_previous = current->prev;

if(current_previous == NULL)
{
// Change the First Node
first = minimum;
}
if(current->next == minimum)
{
// Nodes are Adjacent
minimum->prev = current_previous;
minimum->next = current;

current->prev = minimum;
current->next = min_next;

if(min_next)
{
min_next->prev = current;
}
if(current_previous)
{
current_previous->next = minimum;
}
}
else
{
minimum->prev = current_previous;
minimum->next = current_next;

current->prev = min_previous;
current->next = min_next;

if(current_next)
{
current_next->prev = minimum;
}
if(min_previous)
{
min_previous->next = current;
}
if(min_next)
{
min_next->prev = current;
}
if(current_previous)
{
current_previous->next = minimum;
}
}
current = minimum;
}
}

}
};

int main()
{
LinkList list;

cout<<"LinkList = ";

list.Display();

cout<<"\n\nSorting \n\n";

list.Sort();

cout<<"LinkList = ";

list.Display();
return 0;

}
----- code ends----


I know it sounds easy, and should be easy.. but I am getting all kind
of warnings and errors..if you have better code please help me with
it..


my goal is just to have the merge sort function on the second code to
work on the first one along with bubble sort..I will add an option to
the user to choose which one he wants to perform..the idea is to
measue the speed of the merge sort and the bubble sort..we all know
merge sort is faster..but I just want to demo it

I run my code like this
g++ bubblesort.cpp -o bs.o
then I feed it a list of numbers like this
more list.txt | ./bs.out



thank you very much for your time
 
N

Nick Keighley

Subject "Merge Sort on linked list..my code is almost done..please
help me on it"

how do you know its "almost done"? You might be days off completing
it.


I have worked on this code hours, and get it to work finally on Linux
Debian..

if it's working why do you need help?

its basically sort a linked list --bubble sort.

so, is it bubble sort or merge sort. What did the homework question
say? If they asked for merge sort and you give 'em bubble sort you
might get an F.
Also I added a piece
of code to the main function to measure the execution time of the
bubble sort function

I'd get it to work before I worried about how fast it was.
what I am trying now is to get a merge sort from another source code
and have it to work on mine and measure the time of execution too

ah, you're trying to compare merge sort and bubble sort?
here is my code --

#include <iostream>
#include <time.h>

using namespace std;
class node
{
    friend class linklist;
    int value;
    node *next;

};

right. You see this isn't C and you've posted it to comp.lang.c, you
need to post it to comp.lang.c++. And make it a bit clearer what you
are trying to do and what you want.

class linklist
{
    private:
        node *first;
        node *last;
    public:
        linklist(){ first = NULL; }
        ~linklist(){};
        void addnode();
        void BubbleSort();
        //void MergeSort();
        void displaynode();

    };

void linklist :: displaynode()
{
  //cout<<"---------------------\nSorted values :\n";
  node *curno=first;
  while(curno)
  {
     cout<<curno->value<<'\n';
     curno=curno->next;
  }

}

isn't this misnamed? Doesn't it display the entire list?

<snip>

bless you

    void linklist ::MergeSort()
{

      // your help here please

find the merge sort algorithm (a book or wiki) and code it up to match
your list implementation.

and here is the merge sort code from another program..I just want to
get the merge function in this code to work on mine..my code is the
first one ..the one above

--merge sort -- code--------
#include <iostream>
using namespace std;

#define NULL 0

class LinkList
{
private:
    struct Node
    {
        Node* prev;
        int value;
        Node *next;
    };
    Node *first;

well the nodes are different for a start, you're going to have to
reconcile them somehow. I really would start with a description of the
algorithm

I know it sounds easy, and should be easy..

well no actually. Getting two bits of incompatible software to play
well together is *not* always easy.
but I am getting all kind of warnings and errors..

such as?

if you have better code please help me with it..

my goal is just to have the merge sort function on the second code to
work on the first one along with bubble sort..I will add an option to
the user to choose which one he wants to perform..the idea is to
measue the speed of the merge sort and the bubble sort..we all know
merge sort is faster..but I just want to demo it

putting something like that at the beginning would have saved me some
confusion.
 
C

c

Subject "Merge Sort on linked list..my code is almost done..please
help me on it"

how do you know its "almost done"? You might be days off completing
it.



if it's working why do you need help?


so, is it bubble sort or merge sort. What did the homework question
say? If they asked for merge sort and you give 'em bubble sort you
might get an F.


I'd get it to work before I worried about how fast it was.


ah, you're trying to compare merge sort and bubble sort?





right. You see this isn't C and you've posted it to comp.lang.c, you
need to post it to comp.lang.c++. And make it a bit clearer what you
are trying to do and what you want.






isn't this misnamed? Doesn't it display the entire list?

<snip>

bless you




find the merge sort algorithm (a book or wiki) and code it up to match
your list implementation.

<snip>







well the nodes are different for a start, you're going to have to
reconcile them somehow. I really would start with a description of the
algorithm



well no actually. Getting two bits of incompatible software to play
well together is *not* always easy.


such as?



putting something like that at the beginning would have saved me some
confusion.

first of all, this is not an assignment, second..you should have save
your time and didn't reply to my post..you would have saved me time
too.. id*^&
 
A

Andrew Poelstra

On 2010-04-26 said:
first of all, this is not an assignment, second..you should have save
your time and didn't reply to my post..you would have saved me time
too.. id*^&

You quoted 140 lines of (perfectly valid) commentary just to
tack "**** you, Nick" to the end of his message? I can assure
you that he is not the one who is wasting anyone's time.
 
N

Nick Keighley

You quoted 140 lines of (perfectly valid) commentary just to
tack "**** you, Nick" to the end of his message? I can assure
you that he is not the one who is wasting anyone's time.

I think I might have been wasting mine
 
O

osmium

C wrote:

and here is the merge sort code from another program..I just want to
get the merge function in this code to work on mine..my code is the
first one ..the one above

--merge sort -- code--------
#include <iostream>
using namespace std;

#define NULL 0

Doesn't that look ugly to you? Take it out.

class LinkList
{
private:
struct Node
{
Node* prev;
int value;
Node *next;
};
Node *first;

public :

LinkList()
{
Node *t1 = new Node();
t1->prev = NULL;
t1->value = 4;

Now you should get suspicious. The data are built into the program! That is
not a good starting point for program re use. My guess is that there are
better samples on the Web that you could use, but this one seems to work (it
compiles and runs OK) and you could modify it.

Some tipss:
You posted a lot of chaff, such as the timing check. Such as the bubble
sort. Remove chaff before posting.
Don't post things that require a significant rewrite - which is what you
have done here. You have made no attempt to integrate program A and program
B.
Post to the right group, comp.lang.c++ in this case.
Don't be amazed when you get help that doesn't seem helpful. That happens
from time to time on Usenet. Like 90% of the time.
 
K

Keith Thompson

c said:
I have worked on this code hours, and get it to work finally on Linux
Debian..
its basically sort a linked list --bubble sort. Also I added a piece
of code to the main function to measure the execution time of the
bubble sort function

what I am trying now is to get a merge sort from another source code
and have it to work on mine and measure the time of execution too


here is my code --

#include <iostream>
#include <time.h>

using namespace std;
class node
[snip]

You want comp.lang.c++. We can't help you here.
thank you very much for your time

You're welcome.
 
S

SG

  void linklist::MergeSort()
{
      // your help here please
      // your help here please
      // your help here please
      // your help here please
}

Let's just ignore that this isn't C. A merge sort of a linked list
isn't that hard and there will hardly be a significant difference
between the C version and the C++ version. I think it's okay to get
you started with a top-level view:

/**
* splits a singly-linked list into two lists. Every 2nd
* node of the main list will be MOVED to the 2nd list.
*/
void split(node** beg_main, node** beg2);

/**
* will merge two lists. It MOVES elements from 2nd list
* to 1st list. *beg2 will be a null pointer afterwards.
*/
void merge(node** beg_main, node** beg2);

void merge_sort(node** begin)
{
assert(begin); /* we're expecting a non-NULL pointer */
if (!*begin) return; /* empty lists are already ordered */
node* beg2 = NULL;
split(&begin,&beg2);
merge_sort(&begin);
merge_sort(&beg2);
merge(&begin,&beg2);
assert(beg2 == NULL); /* no elements left in list2 */
}

In C++ you might want to use references to pointers instead. This
pointer-to-pointer or reference-to-pointer trick is really convenient
as it allows you to get away with less special case handling. It's up
to you to figure out, how split(..) and merge(..) works exactly (dirty
work).

Inside your linklist::MergeSort you could write "merge_sort(&first);"
and update the data member named "last" afterwards.

Cheers,
SG
 
S

SG

  /**
   * splits a singly-linked list into two lists. Every 2nd
   * node of the main list will be MOVED to the 2nd list.
   */
  void split(node** beg_main, node** beg2);

  /**
   * will merge two lists. It MOVES elements from 2nd list
   * to 1st list. *beg2 will be a null pointer afterwards.
   */
  void merge(node** beg_main, node** beg2);

  void merge_sort(node** begin)
  {
    assert(begin);       /* we're expecting a non-NULL pointer */
    if (!*begin) return; /* empty lists are already ordered */
    node* beg2 = NULL;
    split(&begin,&beg2);
    merge_sort(&begin);
    merge_sort(&beg2);
    merge(&begin,&beg2);
    assert(beg2 == NULL); /* no elements left in list2 */
  }

OK, that's not correct. Replace "&begin" inside the function body of
merge_sort with "begin". It's already a pointer to a node-pointer.
Maybe there are other issues. I'll let you figure it out. I hope the
idea is clear.
 
S

Seebs

You quoted 140 lines of (perfectly valid) commentary just to
tack "**** you, Nick" to the end of his message? I can assure
you that he is not the one who is wasting anyone's time.

Exactly. Nick gave you a very helpful response, pointing out some issues
that you could clearly benefit from being aware of.

I happen to have debugged and written several merge sorts for linked lists,
but I find myself suddenly uninterested in offering advice. Huh. Who
would have thought that being rude to people wouldn't win you friends?

-s
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,790
Messages
2,569,637
Members
45,346
Latest member
EstebanCoa

Latest Threads

Top