hi i really need help i am really lost in this program if any one can help me with it plz contact me on my email <<mail id snipped>>
(using c++ program)
1. Write a computer program that implements the recursive merge sort.
The input to the program must be a small list of elements (e.g. 10 to 20 integer numbers). The program must sort the input list and produce a sorted list using the recursive merge sort.
The program must first display the list to be sorted. The program must also display the sublists into which the original list is split during the recursive merge sort process. The program must also display the lists into which the sublists are subsequently merged to form the final sorted list.
2. Big-O estimate of the merge sort.
Give a big-O estimate of the complexity of the merge sort algorithm that you wrote. Justify your big-O estimate of the complexity of the merge sort algorithm with reference to the splitting process of the merge sort and the subsequent merge of these sublists into the final sorted list as illustrated by your program output
rouba
- 3 Contributors
- forum3 Replies
- 4 Views
- 9 Years Discussion Span
- comment Latest Post by ithelp
SeeTheLite 20
Ironically I just wrote a merge sort program for queues a few days back, I'll send it to you tomorrow when I'm at school.
rouba
#include<conio.h>
#include<iostream>
using namespace std;
void swap(int &, int &);
void mergeSort(int [],int, int);
int sliptList(int [], int , int);
int main()
{
int size,x;
int nums[size];
cout<<"Please enter the size of your number list: ";
cin>>size;
while(size < 10 || size > 20)
{
cout<<"\nPlease reenter, the size of your list should be between 10 and 20: ";
cin>>size;
}
cout<<"\nPlease enter in the number of your list: ";
for(x=0; x<size; x++)
{
cin>>nums[x];
}
cout<<"\nThe list you have entered is: ";
for (x=0; x<size; x++)
cout<<nums[x]<< " ";
cout<<"\n\nThe two sublists: ";
for (x=0; x <(size/2); x++)
cout<<nums[x]<< " ";
cout<<" || "; // symbol for seperating the two sublists
for (x=(size/2); x <size; x++)
cout<<nums[x]<< " ";
mergeSort(nums, 0, size-1);
cout<<"\n\nThe final sorted list: ";
for (x=0; x<size; x++)
cout<<nums[x]<< " ";
cout<<endl;
cout<<"\nThe big O-estimate in merge sort of a list of n-elements is nlog(n)";
cout<<"\nBig O-estimate in this case is "<<size<<" log "<<size;
getch();
}
void mergeSort(int nums[] ,int start ,int stop) //it ie the recursive function
{
int midpt;
if(start < stop)
{
int sliptList(int [], int , int);
midpt = splitList(nums , start, stop);
mergeSort(nums , start, midpt-1);
mergeSort(nums , midpt+1, stop);
} // ends if
} // ends mergeSort function
int splitList(int nums[], int start, int stop) //accepting array of integers and two integers representing
// the starting and ending subscripts in the list
{
int midval, midpt, mid, x;
mid = (start + stop)/ 2; //the middle position
swap(nums[start], nums[mid]);
midpt = start;
midval = nums[start];
for(x= start + 1; x<=stop; ++x)
{
if(nums[x] < midval)
{
++midpt;
swap(nums[midpt],nums[x]);
}
}
swap(nums[start], nums[midpt]);
return midpt;
}
void swap(int &val1, int &val2)
{
int temp;
temp = val1;
val1 = val2;
val2 = temp;
}
Edited
by Reverend Jim: Fixed formatting
ithelp 757
You neeed to merge the sorted split arrays.