**
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.

3) Short answers:

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[50];

System.out.println(a[22]);

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)

System.out.println(getQuadrant(p1)); // prints 1 as (2,3) is in Quadrant 1

System.out.println(p2); // prints (6,-1)

System.out.println(getQuadrant(p2)); // prints 4 as (6,-1) is in Quadrant 4

Point p3 = p1.midpointTo(p2); // p3 is halfway between p1 and p2

System.out.println(p3); // prints (4, 1)

5) Bonus/Optional

a)
Write a method that takes an array of ints and returns the maximum number
of steps that binary search would require to find an element in the given array.

b)
“Ternary search” (an invented term) works by making *two* guesses at
each step – one guess 1/3^{rd} of the way and a second guess 2/3^{rds}
of the way from lo to hi. Then lo and hi are adjusted in the obvious way. We
don’t teach ternary search because it’s more complicated than binary search yet
it runs just as fast. Using some big-O-like argument (with at least some math,
if also some handwaving), explain this.