View Question
 Question
 Subject: algorithm problems: Merge sort Category: Computers > Algorithms Asked by: levymoshe-ga List Price: \$20.00 Posted: 22 Mar 2006 07:38 PST Expires: 02 Apr 2006 13:46 PDT Question ID: 710538
 ```Two questions 1)Write a merge sort program that run in O(n log n) in C++ 2)use BFS on a directed graph to find the length of the path with the fewest number of edges between two given vertices. The input file name will be specified by the user, either on the command line or upon being prompted by your program. The input file will start with an integer, N, which gives the number of vertices in the graph. The vertices are labeled 0 through N-1. Next will come an even number of integers, where each pair represents an edge in the graph from the first vertex in the pair to the second. All integers in the file are separated by white space (space, tab or newline). Here is an example, 5 0 2 1 2 2 4 2 3 3 4 and the user will also specify the start vertex and end vertex of the path. If there is no path from the start vertex to the end vertex then print that out, otherwise print out the minimum number of edges. EVERYTHING IN C++```
 ```Sorry to sound like a hall monitor, but researchers won't do your homework for you, and neither will the users, especially considering how underpriced this question is. This would take even a good programmer with soild data structures/algorithms experience 3 hours to write and verify. Also, you didn't specify what kind of data structure the merge sort will be sorting.```
 ```try this code as it may help you problem 1)Merge sort // merge sort // run using turbo c/c++ compiler #include #include #define N 1000 void msort(int *,int ,int ); void merge(int *,int ,int ,int ); void main() { int array[N],i,j,len; clrscr(); cout<<"Enter the length of list to be sorted :: "; cin>>len; cout<>array[i]; } msort(array,0,len-1); cout<<"\n The sorted list is ::\n"; for(i=0;i #include #include #include #include #include #include #define MAX 100 //Function Declarations void createdb(); void route(char *to); void assert_path(char *from,char *to); void push(char *from,char *to); void pop(char *from,char *to); int ispath(char *from,char *to); int find(char *from,char *anywhere); int find1(char *from,char *anywhere); int match(char *from, char *to); //Structure for path datbase struct pt { char from[4]; char to[4]; char skip; //for back tracking char tskip; //for temp back tracking }; struct pt path[MAX]; int p_pos=0; //number of emtries in path database int find_pos=0; //index for searching path database int tos=0; //top of stack struct stack { char from[4]; char to[4]; }; struct stack bt_stack[MAX]; //back track stack void main() { clrscr(); char from[4],to[4]; createdb(); cout<<"\n\n\nEnter Start vertex :: "; gets(from); cout<<"\n\nEnter End vertex :: "; gets(to); if(ispath(from,to)==1) { cout<<"\n\nThe path is.........\n\n"; route(to); } else cout<<"\n\nThere is no path from :: "<>file; cout< internal enteries greater than total number of vertices....\n"; getch(); exit(0); } flag=0; } if(count%2!=1) { cout<<"\n\nEntries are not correct in the file...\n"; exit(0); } else cout<<"\n\nCreating database...........\n\n"; // Enter Graph Data in.close(); in.open(file); char from[4],to[4]; flag=1; in.get(ch); while(in) { while(in &&(ch==' '||ch=='\t'||ch=='\n')) in.get(ch); if(flag==1) { while(in && !(ch==' '||ch=='\t'||ch=='\n')) { in.get(ch); flag=0; } } else { len=0; while(in && !(ch==' '||ch=='\t'||ch=='\n')) { from[len]=ch; len++; in.get(ch); } from[len]='\0'; while(in &&(ch==' '||ch=='\t'||ch=='\n')) in.get(ch); len=0; while(in && !(ch==' '||ch=='\t'||ch=='\n')) { to[len]=ch; len++; in.get(ch); } to[len]='\0'; cout<<"\nFrom : "<-1;t--) if(!strcmp(path[t].from,from)&&!strcmp(path[t].to,to)) return 1; return 0; //not found } //Given from, find anywhere.. int find(char *from,char *anywhere) { find_pos=0; while(find_pos0) { //backtrack pop(from,to); if(ispath(from,to)) return 1; } } //Stack Routines void push(char *from,char *to) { if(tos0) { tos--; strcpy(from,bt_stack[tos].from); strcpy(to,bt_stack[tos].to); } else cout<<"\nStack Underflow....."; }```