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.