CS 151 -- Lab Oct 26

Part 1--Hand Simulation

Show the array after each step of selection sort, insertion sort and heap sort for the list below.
For insertion and selection sort, use the in-place algorithms discussed in class.
For heap sort, show the array after each addition to the heap and each removal from the heap.
Using your work above, count the number of operations you did for each of these sorts:

comparisons (greater than, less than, equals) count as 1
swap count as 3

Part 2 -- Merging

Write a method with the following signature:

        public String[] merge(String[] arr1, String[] arr2)

That is the method takes two arrays that each hold items of String. The result should be an array whose length is equal to the length of the two input arrays. Further, the resulting array should have the following arrangement. So long are there remains items in both arrays, put 2 items from the first array into the output array, then one from the second. Repeat. When one array is exhaused, put the remaining items from the second array into the output array. For instance,

        input array 1:  a,b,c,d,e,f,g,h,i,j,k
        input array 2:  A,B,C,D,E,F,G
        returned array: a,b,A,c,d,B,e,f,C,g,h,D,i,j,E,k,F,G

A call to this function might look like:

        String[] aa = {"a","b", "c", "d", "e", "f", "g", "h", "i", "j", "k"};
        String[] bb = {"A", "B", "C", "D", "E", "F", "G"};
        String[] cc = new Merger().merge(aa, bb);

What to turn in

Send email to gtowell151@cs.brynmawr.edu with you final operation counts from part 1 and your code from part 2.