Merge Sort on linked list..my code is almost done..please help me on
it
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-
next)
{
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