Almost got this program to work. Still have one error but not sure how to fix.
It is using a linked list class for storing nodes. Here is the code:
// functions use by main
void mergesort(linked_list& list);
// Merges sorted list dl1 and dl2 into a sorted list dl
void merge(linked_list& list1, linked_list& list2, linked_list& list);
// merge sort on link list
void mergesort(linked_list& list)
{
int i;
int d;
linked_list list1;
linked_list list2;
int n = list.size();
if(n < 2)return;
// copy 1/2 to list1
for (i=1; i <= (n+1)/2; i++)
{
d = list.get_first();
list.remove(0);
list1.add_last(d);
}
// copy remaining 1/2 to list2
for (i=1; i <= n/2; i++)
{
d = list.get_first();
list.remove(0);
list2.add_last(d);
}
// sort both lists by recursion
mergesort(list1);
mergesort(list2);
// merge two lists
merge(list1,list2,list);
}
// Merges sorted list dl1 and dl2 into a sorted list dl
void merge(linked_list& list1, linked_list& list2, linked_list& list)
{
int d,d1,d2;
// loop till both lists empty
while(!list1.size()==0 && !list2.size()==0)
{
// get data items from start of both lists
d1 = list1.get_first();
d2 = list2.get_first();
// check if first element of dl1 is less than dl2
// from list1
if(d1 < d2)
{
d = list1.get_first();
list1.remove(0);
list.add_last(d);
}
// from list2
else
{
d = list2.get_first();
list2.remove(0);
list.add_last(d);
}
}
// empty list dl1 into dl
if(list1.size()==0)
{
// get rest of list2
while(!list2.size()==0)
{
d = list2.get_first();
list2.remove(0);
list.add_last(d);
}
}
// empty list dl2 into dl
if(list2.size()==0)
{
// get rest of list1
while(!list1.size()==0)
{
d = list1.get_first();
list1.remove(0);
list.add_last(d);
}
}
}
int main(void)
{
int ar[100];
int i, v, len;
for (i=0; i<100; i++) {
cout << "enter a number (-1 to quit): ";
cin >> v;
if (v < 0) break;
ar[i] = v;
}
len = i;
cout << "main: before sort:\n";
for (i=0; i<len; i++) {
cout << "main: ar[" << i << "] = " << ar[i] << endl;
}
mergesort ms(ar, len);
cout << "main: after sort:\n";
for (i=0; i<len; i++) {
cout << "main: ar[" << i << "] = " << ar[i] << endl;
}
}
Here is the error:
Hlab8.cpp: In function `int main()':
lab8.cpp:305: error: `mergesort' undeclared (first use this function)
lab8.cpp:305: error: (Each undeclared identifier is reported only once for each
function it appears in.)
lab8.cpp:305: error: syntax error before `(' token
make: *** [lab8] Error 1