15-110 Sections G-J / Spring 2010 / Quiz 6
4 Questions / 25 Minutes

1)      Write a swap method to swap two elements in an array of Strings.

2)      Write a bubblesort method that sorts an array of Strings by their lengths (shortest first), with ties (same-length Strings) arranged alphabetically.  You may use the swap method you just wrote.

a)      Name a sort that does not use an auxiliary array, but which may swap elements that are not adjancent (next to each other).

b)      List the values (not the indexes), in order, of the guesses that binary search would make in order to find the number 32 in this array:  {  2, 4, 13, 22, 32, 41, 1099 }

c)      Say you have an alphabetized list of everyone on Earth (all 6.6 billion of us).  What is the most number of guesses binary search would have to make to find a name in that list?

d)      In class, we noted that bubblesort requires only one quick pass on an already-sorted list.  Name another sort that has that same behavior.

e)      Draw a picture similar to xSortLab’s output of what an array might look like after mergesort has run for a while but still has two more passes to go (so the array is partially, but not completely sorted).

f)       What will the following code print?
Polygon[] a = new Polygon;
System.out.println(a);

4)      Write a class that models a (two-dimensional) Point on a plane (we’ll just use integer values, so technically these are “lattice points”).  In particular, write the least amount of code to make this example work:
Point p1 = new Point(2,3);
Point p2 = new Point(6,-1);
System.out.println(p1);              // prints (2,3)