Solved

A question about Merge Sort

Posted on 2011-03-01
11
416 Views
Last Modified: 2012-05-11
Hey,

       I was trying to write a merge sort in C++, and this is what I got:

index size(number_sequence S) { return S.length; }

void merge_sort(number_sequence S) {                    
        index n = size(S);
        if (n < 2) return;              
        index mid = n/2;

        // Sort the two halves separately.                                      
        merge_sort(subseq(S, 1, mid));
        merge_sort(subseq(S, mid+1, n));

        // Merge the two sorted halves.                                        
        merge(S, mid);
}

void merge(number_sequence S, index mid) { // Solve the Merge problem.                                                       

        index n =size(S);                                                           
        number* p = new number[n];
        number_sequence A, B; 
        A.init(p, mid); 
        B.init(p+mid, n-mid);
        copy(A, subseq(S, 1, mid));
        copy(B, subseq(S, mid+1, n));
                                                                   
        index a=1, b=1;
        for (index k = 1; k <= n; ++k) {
                if (a <= mid and b <= n-mid)                                                        
                        if (A[a] < B[b]) S[k] = A[a++];
                    else             S[k] = B[b++];
        else if (a <= mid)                                                                      
                        S[k] = A[a++];
                else                                                                             
                        break;                                                                 
        }
        delete p; // Deallocate work space.                                                                                  
}

Open in new window


But, my professor says it copies things more than it should... but I don't understand why that would be... I built my code from what I found here http://en.wikipedia.org/wiki/Merge_sort .

Could anyone give me a hint as to where I messed up?

Thanks in advance!
0
Comment
Question by:errang
  • 5
  • 3
  • 2
  • +1
11 Comments
 
LVL 32

Expert Comment

by:phoffric
ID: 35008461
subseq ??
Could you post your whole buildable program including test driver.
0
 
LVL 16

Accepted Solution

by:
imladris earned 250 total points
ID: 35008541
You're copying S into A and B. Couldn't you operate on S directly, and then push the selected element to a single new sequence N?

        for (index k = 1; k <= n; ++k) {
                if (a <= mid and b <= n-mid)                                                        
                        if (S[a] < S\[b\]) N[k] = S[a++];
                    else             N[k] = S[b++];
 
0
 

Author Comment

by:errang
ID: 35009080
No... He was kinda specific about not touching anything else...

But... I was thinking,

for (index k = 1; k <= n; ++k) {
                if (a <= mid and b <= n-mid)                                                        
                        if (A[a] < B[b]) S[k] = A[a++];
                    else             S[k] = B[b++];
        else if (a <= mid)                                                                      
                        S[k] = A[a++];
                else                                                                             
                        break;                                                                 
        }

Open in new window


this loop is going from k = 1 to k<=n... but all a merge sort needs is to split the given sequence in half and sort the halves... right?

Would it be as simple as changing the boundaries of the loop? It seems to be copying things more than it should.
0
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 33

Assisted Solution

by:sarabande
sarabande earned 250 total points
ID: 35009118
the first unneeded copy is cause you pass the S by value and not by reference.

the second is the p array where i can't see any practical benefit (and must be delete []p; at end)

then A and B were used only for read purposes. it was some time ago when i implemented merge sort myself. but i am pretty sure you don't need the A and B but only a swap function, cause you can do the read operations on the input sequence.

what i don't understand is that all assignments were made to S which is a local copy. how does the caller get the sorted values back? is the copy constructor of number_sequence using same internal pointer????

Sara
0
 

Author Comment

by:errang
ID: 35009129
>>You're copying S into A and B. Couldn't you operate on S directly, and then push the selected element to a single new sequence N?

Sorry... I'm not sure I follow that.
0
 

Author Comment

by:errang
ID: 35009185
>>what i don't understand is that all assignments were made to S which is a local copy. how does the caller get the sorted values back? is the copy constructor of number_sequence using same internal pointer????

Yea, number_sequence is a struct.
0
 
LVL 33

Expert Comment

by:sarabande
ID: 35009311
is it C or C++?

in case of c++ a struct is same as a class and if you don't provide an own copy constructor the compiler creates one for you. all those copies would use same pointer what means you can't delete it in destructor. that is really bad code technique even if it is c. In c you would have one instance of structure and pass a pointer to that structure. in c++ you pass the struct/class by reference.

Sara
0
 

Author Comment

by:errang
ID: 35009467
It is C++
0
 
LVL 16

Expert Comment

by:imladris
ID: 35009513
>>>You're copying S into A and B. Couldn't you operate on S directly, and then push the selected element to a single new sequence N?

>Sorry... I'm not sure I follow that.

What I was proposing is that you use S directly in the central loop; rather than first copying to A and B; see the code snippet I provided.

Sarabande point about passing by value, rather than by reference, is also relevant.
0
 

Author Comment

by:errang
ID: 35009993
>>What I was proposing is that you use S directly in the central loop; rather than first copying to A and B; see the code snippet I provided

Ah... I see it now, will have to change the starting index of b for that to work... I'll try that out.
0
 
LVL 33

Expert Comment

by:sarabande
ID: 35010298
also change interface of functions to

  void merge_sort(number_sequence & S);

  void merge(number_sequence & S, index mid);

  index size(number_sequence & S);

  void copy(number_sequence & S1, number_sequence & S2);

  number_sequence & subseq(number_sequence & S1, int start, int end);

Sara
   
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
convert char array to number in c 5 86
change colour of repeater control in asp.net c# 7 111
Constant string is of type char *   ? 7 42
I could not set window to top 4 20
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question