CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Oct 2012
    Posts
    18

    I'm having trouble with my Merge Sort - tried it a couple different ways and this sma

    I have created a program that first sorts a series of numbers that are input dynamically then an option is given to either use a sequential search or a Binary search. my sequential search works fine but the merge sort coupled with the binary search has a small bug that I just can't seem to figure how to eliminate. I first used my own merge sort but it was really in efficient so a I took a more effient example and incorporated it in my program but I cant seem to get rid of this bug I'm dealing with. and it seems to be causing a futher problem with the Binary seach. I have entered the ful code (sorry about the length) and I'm hoping anybody can lead me in the right direction towards fixing this.

    here's my code

    Code:
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    const int N = 10;
    
    // A simple print function
    void print(int *A)
    {
        for ( int i = 0; i < N; i++ )
            cout << A[i] << " ";
        cout << endl;
    }
    
    void merge(int* A, int p, int r)
    {
        int mid = floor((p + r) / 2);
        int i1 = 0;
        int i2 = p;
        int i3 = mid + 1;
    
        // Temp array //////I tried this two different ways but nothing seems to work
    	//int temp [r-p+1];
        int temp = new int[r-p+1];
    
        // Merge in sorted form the 2 arrays
        while ( i2 <= mid && i3 <= r )
            if ( A[i2] < A[i3] )
                temp[i1++] = A[i2++];
            else
                temp[i1++] = A[i3++];
    
        // Merge the remaining elements in left array
        while ( i2 <= mid )
            temp[i1++] = A[i2++];
    
        // Merge the remaining elements in right array
        while ( i3 <= r )
            temp[i1++] = A[i3++];
    
        // Move from temp array to master array
        for ( int i = p; i <= r; i++ )
            A[i] = temp[i-p];
    }
    
    void merge_sort(int* A, int p, int r)
    {
        if ( p < r )
        {
            int mid = floor((p + r) / 2);
            merge_sort(A, p, mid);
            merge_sort(A, mid + 1, r);
            merge(A, p, r);
        }
    }
    int sSearch(int A[], int N, int V)
    {
    	for(int i=1;i<=N; i=i+1)
    	{
    		if (V==A[i]){
    			cout<<"Data found at position:  "<<i<<endl;
    		return i;
    		}
    	}
    }
    int bSearch(int A[], int p, int r, int V)
    {
    	if (p<r)
    		{
    		int mid =(p+r)/2;
    			if(V==A[mid])
    				return mid;
    					else if (V<A[mid])
    						return bSearch(A, p, mid-1,V);
    							else 
    						return bSearch(A, mid+1, r, V);
    					}
    				if (V==A[p])
    		return p;
    	else return-1;
    }
    
    int main(){
    	
    		int N, i, V, option, p, r;
    		cout<<"Please enter the size of Array "<<endl;
    				cin>>N;
    					int* A ;
    					A= new int[N];
    					cout<<"Please enter each numerical value "<<endl;
    						for(i=1;i<=N;i++)
    							{
    							cin>>A[i];
    							
    							}
    						merge_sort(A, 0, 9);
    						cout<<A<<endl;
    		cout<<"Choose the desired task to perform"<<endl;
    		cout<<"For Sequence Search select: (option 1)"<<endl;
    		cout<<"For Binary Search select: (option 2)"<<endl;
    		cin>>option;
    		cout<<endl;
    			if(option ==1)
    				{
    					cout<<"Please enter the digit you are searching for "<<endl;
    						cin>>V;
    							cout<<endl;
    							i=sSearch(A, N, V);
    							if (A[i]!=V){
    						cout<<"Value Not Found "<<endl;
    					}
    				}
    					else	if (option ==2)
    						{
    							cout<<"Please enter the digit you are searching for "<<endl;
    								cin>>V;
    									cout<<endl;
    										bSearch(A, p, r, V);
    									if (A[i]!=V){
    								cout<<"Value Not Found "<<endl;
    							}
    						}
    
    system ("PAUSE");
    return 0;
    }
    Can anybody please tell me what I'm pulling out the little hair I got over
    Thank You!!!

  2. #2
    Join Date
    Oct 2012
    Posts
    18

    Re: I'm having trouble with my Merge Sort - tried it a couple different ways and this

    i think i might have accidentally posted twice sorry!!!

  3. #3
    Join Date
    Mar 2011
    Posts
    52

    Red face Re: I'm having trouble with my Merge Sort - tried it a couple different ways and this

    Here is an example I found here:
    http://login2win.blogspot.com/2011/06/merge-sort.html

    I had to change it around a bit to get it to compile, but it is now a working example.

    Code:
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    const int INPUT_SIZE = 10;
    
    // A simple print function
    void print(int *input)
    {
        for ( int i = 0; i < INPUT_SIZE; i++ )
            cout << input[i] << " ";
        cout << endl;
    }
    
    void merge(int* input, int p, int r)
    {
        int mid = (p + r) / 2;
        int i1 = 0;
        int i2 = p;
        int i3 = mid + 1;
    
        // Temp array
        int temp[INPUT_SIZE];
    
        // Merge in sorted form the 2 arrays
        while ( i2 <= mid && i3 <= r )
            if ( input[i2] < input[i3] )
                temp[i1++] = input[i2++];
            else
                temp[i1++] = input[i3++];
    
        // Merge the remaining elements in left array
        while ( i2 <= mid )
            temp[i1++] = input[i2++];
    
        // Merge the remaining elements in right array
        while ( i3 <= r )
            temp[i1++] = input[i3++];
    
        // Move from temp array to master array
        for ( int i = p; i <= r; i++ )
            input[i] = temp[i-p];
    }
    
    void merge_sort(int* input, int p, int r)
    {
        if ( p < r )
        {
            int mid = ((p + r) / 2);
            merge_sort(input, p, mid);
            merge_sort(input, mid + 1, r);
            merge(input, p, r);
        }
    }
    
    int main()
    {
        int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
        cout << "Input: ";
        print(input);
        merge_sort(input, 0, 9);
        cout << "Output: ";
        print(input);
    
    	system("PAUSE");
        return 0;
    }

    Good Luck!

  4. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: I'm having trouble with my Merge Sort - tried it a couple different ways and this

    I had to change it around a bit to get it to compile
    There are also problems with other programs from the same site - some with serious buffer overrun security issues. I don't know what version of c++ is used, but it's not ANSI c++. One of the less serious problems is the expectation of creating a standard array (eg of int) with the number of elements computed at run time!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured