errang
asked on
A question about Merge Sort
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);
}
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!
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
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.
}
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!
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
No... He was kinda specific about not touching anything else...
But... I was thinking,
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.
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;
}
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
>>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.
Sorry... I'm not sure I follow that.
ASKER
>>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.
Yea, number_sequence is a struct.
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
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
ASKER
It is C++
>>>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.
>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.
ASKER
>>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.
Ah... I see it now, will have to change the starting index of b for that to work... I'll try that out.
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
void merge_sort(number_sequence
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
Could you post your whole buildable program including test driver.