Google Answers Logo
View Question
 
Q: algorithm problems: Merge sort ( No Answer,   2 Comments )
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++
Answer  
There is no answer at this time.

Comments  
Subject: Re: algorithm problems: Merge sort
From: frankcorrao-ga on 22 Mar 2006 13:57 PST
 
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.
Subject: Re: algorithm problems: Merge sort
From: ashish_o4u-ga on 29 Mar 2006 20:17 PST
 
try this code as it may help you
 
problem 1)Merge sort
// merge sort

// run using turbo c/c++ compiler

 #include<iostream.h>

#include<conio.h>

#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<<endl<<endl;

for(i=0;i<len;i++)

{

cout<<"Enter number "<<i+1<<" of the list :";

cin>>array[i];

}

msort(array,0,len-1);

cout<<"\n The sorted list is ::\n";

for(i=0;i<len;i++)

{

cout<<array[i]<<" ";

}

getch();

}

void msort(int array[],int low,int high)

{

int mid;

if(low<high)

{

mid=(low+high)/2;

msort(array,low,mid);

msort(array,mid+1,high);

merge(array,low,mid,high);

}

}

void merge(int array[],int low,int mid,int high)

{

int i,j,k=low;

int temp_arr[N];

i=low;

j=mid+1;

while(i<=mid&&j<=high)

{

if(array[i]<array[j])

temp_arr[k++]=array[i++];

else

temp_arr[k++]=array[j++];

}

while(i<=mid)

temp_arr[k++]=array[i++];

while(j<=high)

temp_arr[k++]=array[j++];

for(i=low;i<=high;i++)

array[i]=temp_arr[i];

}

 

//*****************************************************************************

//*****************************************************************************

//Problem2

// run Code using turbo c/c++ compiler

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

#include<fstream.h>

#include<process.h>

#include<stdlib.h>

#include<string.h>

#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 :: "<<from<<" to "<<to;

getch();

}

//Function Definations

//Initialize path database

void createdb()

{

char ch,*file;

cout<<"Enter the file name :: ";

cin>>file;

cout<<endl<<endl;

ifstream in(file);

if(!in)

{

cout<<"Unable to open file........\n";

getch();

exit(0);

}

int ch1,len,count=0,flag=1,n;

char vertex[4];

in.get(ch);

while(in)

{

len=0;

while(in&&!(ch==' '||ch=='\t'||ch=='\n'))

{

vertex[len]=ch;

len++;

in.get(ch);

}

vertex[len]='\0';

while(in&&(ch==' '||ch=='\t'||ch=='\n'))

in.get(ch);

count++;

if(flag==1 && vertex!='\0')

{

n=atoi(vertex);

}

if(n<=atoi(vertex) && flag==0)

{

cout<<"\n\n Wrong entries :> 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 : "<<from<<" to "<<to;

assert_path(from,to);

}

}

in.close();

}

//Enter facts into database

void assert_path(char *from,char *to)

{

if(p_pos<MAX)

{

strcpy(path[p_pos].from,from);

strcpy(path[p_pos].to,to);

path[p_pos].skip=0;

path[p_pos].skip=0;

p_pos++;

}

else

cout<<"\nPath database full.......\n";

}

//Show the route

void route(char *to)

{

int t=0;

cout<<endl;

while(t<tos)

{

cout<<bt_stack[t].from<<" to ";

t++;

}

cout<<to;

}

//if path between from and to than return 1 else 0

int match(char *from,char *to)

{

register int t;

for(t=p_pos-1;t>-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_pos<p_pos)

{

if(!strcmp(path[find_pos].from,from) &&!path[find_pos].skip)

{

strcpy(anywhere,path[find_pos].to);

path[find_pos].skip=1; //make active

return 1;

}

find_pos++;

}

return 0;

}

int find1(char *from,char *anywhere)

{

find_pos=0;

while(find_pos<p_pos)

{

if(!strcmp(path[find_pos].from,from) &&!path[find_pos].tskip)

{

strcpy(anywhere,path[find_pos].to);

path[find_pos].tskip=1; //make active

return 1;

}

find_pos++;

}

return 0;

}

//Determine if there is route between from and to..

int ispath(char *from,char *to)

{

char anywhere[4];

//see if at destination

if(match(from,to))

{

push(from,to);

return 1;

}

while(find(from,anywhere))

{

//breath first modification

if(match(anywhere,to))

{

push(from,to);

push(anywhere,to);

return 1;

}

}

//try any connection

if(find1(from,anywhere))

{

push(from,to);

ispath(anywhere,to);

}

else if(tos>0)

{

//backtrack

pop(from,to);

if(ispath(from,to))

return 1;

}

}

//Stack Routines

void push(char *from,char *to)

{

if(tos<MAX)

{

strcpy(bt_stack[tos].from,from);

strcpy(bt_stack[tos].to,to);

tos++;

}

else

cout<<"\nStack full....";

}

void pop(char *from,char *to)

{

if(tos>0)

{

tos--;

strcpy(from,bt_stack[tos].from);

strcpy(to,bt_stack[tos].to);

}

else

cout<<"\nStack Underflow.....";

}

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy