Final

[Grant]

I can code up merge sort in less than thirty minutes (after much
practice) using the code we used in class. This is different than the
pseudo code on the wikipedia site. I am struggling to get the
wikipedia version working.

In the hint email it says to be able to code from the wikipedia pseudo
code. Will I be able to get by using the in class version?
And by "get by" I mean not miss any points on the final.

Thanks!

[William Ingold]

I don't suppose I can see the in class Merge sort code?

I agree, the wikipedia's pseudo code does seem a bit hard to code correctly.
It seemed like the pseudo code for the bubble sort was better written
or something.

[Sarah Morley]

I don't really know what the plan is for the final. You know as much as I do. I would guess that Rob didn't mean that you had to be prepared specifically for the pseudo code on wikipedia, but just pseudo code in general. If you can code it up from another source of pseudo code, I think you're probably fine.

Sarah

[Grant]

Here is the in class stuff:


public class Mergesort {
public static void main(String[] args) {
int[] unsorted = {9,5,2,6,3,9};
int[] sorted = merge_sort(unsorted);
for(int element : sorted){
System.out.print(element + " ");
}
System.out.println();
}
public static int[] merge_sort(int[] unsorted){
// if length(m) ≤ 1
if(unsorted.length <=1){
return unsorted;
}
// var integer middle = length(m) / 2
int middle = unsorted.length / 2;
// var list left, right, result
int[] left = new int[middle];
int[] right = new int[unsorted.length-middle];
int[] result = new int[unsorted.length];
// for each x in m up to middle
// add x to left
for(int i=0; i<left.length; i++){
left[i] = unsorted[i];
}
// for each x in m after middle
// add x to right
for(int i=middle; i < unsorted.length; i++){
right[i-middle] = unsorted[i];
}
left = merge_sort(left);
right = merge_sort(right);
result = merge(left, right);
return result;
}




static int[] merge(int[] left, int[] right){
int[] result = new int[left.length + right.length];
int left_idx = 0;
int right_idx = 0;
int result_idx = 0;
for(int i=0; i<result.length; i++){
if(right_idx == right.length){
result[result_idx]=left[left_idx];
left_idx++;
result_idx++;
}
else if(left_idx == left.length){
result[result_idx]=right[right_idx];
right_idx++;
result_idx++;
}
else if(left[left_idx]<right[right_idx]){
result[result_idx]=left[left_idx];
left_idx++;
result_idx++;
}
else {result[result_idx]=right[right_idx];
right_idx++;
result_idx++;
}
}
return result;
}
}


The main difference is in the second method.

On Aug 5, 3:39 pm, Sarah Morley <sarah_mor...@byu.edu> wrote:
> I don't really know what the plan is for the final. You know as much as I
> do. I would guess that Rob didn't mean that you had to be prepared
> specifically for the pseudo code on wikipedia, but just pseudo code in
> general. If you can code it up from another source of pseudo code, I think
> you're probably fine.
>
> Sarah
>
>
>
> On Fri, Aug 5, 2011 at 3:34 PM, William Ingold <will...@ingold.org> wrote:
> > I don't suppose I can see the in class Merge sort code?
>
> > I agree, the wikipedia's pseudo code does seem a bit hard to code
> > correctly.
> > It seemed like the pseudo code for the bubble sort was better written
> > or something.
>

[Grant]

I think the biggest struggle about the wikipedia stuff for me is the
"append" part.

I don't think we have talked about that... if we have I don't remember
it. My worry is that the final will contain pseudo code for stuff I
don't remember talking about...
What can I do to prepare for that?

On Aug 5, 3:39 pm, Sarah Morley <sarah_mor...@byu.edu> wrote:

> I don't really know what the plan is for the final. You know as much as I
> do. I would guess that Rob didn't mean that you had to be prepared
> specifically for the pseudo code on wikipedia, but just pseudo code in
> general. If you can code it up from another source of pseudo code, I think
> you're probably fine.
>
> Sarah
>
>
>
> On Fri, Aug 5, 2011 at 3:34 PM, William Ingold <will...@ingold.org> wrote:
> > I don't suppose I can see the in class Merge sort code?
>
> > I agree, the wikipedia's pseudo code does seem a bit hard to code
> > correctly.
> > It seemed like the pseudo code for the bubble sort was better written
> > or something.
>

[Sarah Morley]

"append" just means to add on. So, in the wikipedia pseudo code it's just saying to add the number to the result array.

On Fri, Aug 5, 2011 at 4:06 PM, Grant <grant.g...@gmail.com> wrote:

if this is a repost I am sorry:

I am mostly worried that the final will contain pseudo code for stuff
like "append" that I don't remember talking about. How can I prepare
for that?