Friday, March 27, 2015

Having trouble writing a recursive Merge Sort algorithm
































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































I have this assignment to write a Merge Sort algorithm using recursion. To start I have a very tough time picturing what is happening when it comes to recursion, but I do understand how merge sorting works. At the moment I feel as though a very good portion of my code is correct, but I am having trouble with the recursion in the main method [ mergeSort(Queue<T> queue) ].
































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































I have another 4 or so hours to pass in my assignment finished or not, and at this point I can honestly say I have no clue how to make my code work. I tried working through the problem on paper with a simple queue of size 3, but even that is a struggle. On paper my code works perfectly fine, so there is definitely something I am missing.
































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































Below is what I have along with my JUnit test, I am hoping someone can see my flaw, because I have been trying for the past 6 straight hours
































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































Java Code:











































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































private Queue<T> output = new Queue<T>();
private Queue<T> output1 = new Queue<T>();
private Queue<T> output2 = new Queue<T>();

public Queue<T> mergeSort(Queue<T> queue) {
// TODO 1

if(queue.size() <= 1) {
return queue;
} else {
divide(queue, new Queue<T>(), new Queue<T>());

if(output1.size() > 1 && output2.size() > 1) {
return merge(mergeSort(output1), mergeSort(output2));
} else
if(output1.size() > 1 && output2.size() <= 1) {
return merge(mergeSort(output1), mergeSort(output2));
} else
if(output1.size() <= 1 && output2.size() > 1){
return merge(mergeSort(output1), mergeSort(output2));
} else {
return merge(output1, output2);
}
}
}

void divide(Queue<T> input, Queue<T> output1, Queue<T> output2) {
// TODO 2
if(!input.isEmpty()) {
output1.enqueue(input.dequeue());

if(!input.isEmpty()) {
output2.enqueue(input.dequeue());
}
divide(input, output1, output2);
} else {
this.output1 = output1;
this.output2 = output2;
}
}

Queue<T> merge(Queue<T> input1, Queue<T> input2) {
// TODO 3
mergeHelper(input1, input2, new Queue<T>());

return output;
}

void mergeHelper(Queue<T> input1, Queue<T> input2, Queue<T> output) {
// TODO 4
if(!input1.isEmpty() || !input2.isEmpty()) {

if(input2.isEmpty()) {
output.enqueue(input1.dequeue());
} else
if(input1.isEmpty()) {
output.enqueue(input2.dequeue());
} else {
if(input1.peek().compareTo(input2.peek()) < 0) {
output.enqueue(input1.dequeue());
} else
if(input1.peek().compareTo(input2.peek()) == 0) {
output.enqueue(input1.dequeue());
output.enqueue(input2.dequeue());
} else {
output.enqueue(input2.dequeue());
}
}

mergeHelper(input1, input2, output);
} else {
this.output = output;
}

}









































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































JUnit Test with a queue [3, 0, 1]































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































Java Code:











































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































@Test
public void testThree() throws Exception {
Queue<Integer> three = new Queue<Integer>();
three.enqueue(3);
three.enqueue(0);
three.enqueue(1);

Queue<Integer> sorted = new MergeSorter<Integer>().mergeSort(three);

assertEquals((Integer) 0, sorted.dequeue());
assertEquals((Integer) 1, sorted.dequeue());
assertEquals((Integer) 3, sorted.dequeue());
}








































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































No comments:

Post a Comment