Computer Science 15-111 (Sections A & B), Spring 2007

Class Notes: 28-Feb-2007

Logistics

1. Reminder: Quiz 3, #5 (painting outer rectangle is ok) – bring quiz to me!
2. Hw6 posted today and is due in one week (Wed 07-Mar-07)
3. Quiz4 is on Wed 07-Mar-07 and covers:
1. Inheritance (Chapter 7, except 7.4)
2. Linear Search and Binary Search
3. Quadratic Sorts (Insertion, Selection, Bubble)
4. Comparable + Comparator
5. Arrays.sort and Collections.sort
6. Mergesort
4. Test 2 is on Wed 18-Apr-07.
5. Reading: Java by Dissection, Ch 5.6 – 5.8, Ch 7.8
   
   

Topic Outline:

1. How Not To Copy An Array
(or How Not To Drop Rows in Tetris)
for (int row=dropRow; row>0; row--)
board[row-1] = board[row]; // ß WRONG!!!!
A standalone example:
import java.util.*;
import static java.lang.System.out;
class Foo {
public static void main(String[] args) {
int[][] x = { { 1, 0, 1 },
{ 1, 1, 1 } }; // row is "full"
// now we simulate dropping row0 into row1
// and resetting row0 to all 0's:
x[1] = x[0]; // <-- PROBLEM!!! Now row 1 IS row 0!!!
for (int i=0; i<x[0].length; i++)
x[0][i] = 0; // clear row 0 (and row 1 by mistake!)
// now print out the array:
out.println(Arrays.toString(x[0])); // [0, 0, 0]
out.println(Arrays.toString(x[1])); // [0, 0, 0]
}
}

2. Bubblesort: Repeatedly bubble adjacent elements

a. Algorithm:
Each pass: Moving left-to-right, swap each adjacent pair that is out of order.
Repeat passes until no swaps occur.

b. Example:
Original:
4 2 1 3 unsorted array x[]
Pass 1:
4 2 1 3 compare x[0] and x[1]
2 4 1 3 swap them!
2 4 1 3 compare x[1] and x[2]
2 1 4 3 swap them!
2 1 4 3 compare x[2] and x[3]
2 1 3 4 swap them!
Pass 2:
2 1 3 4 compare x[0] and x[1]
1 2 3 4 swap them!
1 2 3 4 compare x[1] and x[2]
1 2 3 4 compare x[2] and x[3]
Pass 3:
1 2 3 4 compare x[0] and x[1]
1 2 3 4 compare x[1] and x[2]
1 2 3 4 compare x[2] and x[3]
SORTED in 13 operations:
4 Swaps + 9 Comparisons

3. Improved Bubblesort

a. Algorithm:
Same as Bubblesort, except:
Notice that after pass k, the rightmost k elements are sorted!

b. Example:
Original:
4 2 1 3 unsorted array x[]
Pass 1:
4 2 1 3 compare x[0] and x[1]
2 4 1 3 swap them!
2 4 1 3 compare x[1] and x[2]
2 1 4 3 swap them!
2 1 4 3 compare x[2] and x[3]
2 1 3 4 swap them!
Pass 2:
2 1 3 4 compare x[0] and x[1]
1 2 3 4 swap them!
1 2 3 4 compare x[1] and x[2]
Pass 3:
1 2 3 4 compare x[0] and x[1]
SORTED in 10 operations:
4 Swaps + 6 Comparisons (reduced from 9 comparisons!)

4. Selectionsort: Repeatedly select smallest element

a. Algorithm:
For each index i from 0 to (n-2):
First, select the smallest element from x[i] to the right.
Then, swap this element with x[i].
Notice that after pass k, the leftmost k elements are sorted!

b. Example:
Original:
4 2 1 3 unsorted array x[]
Pass 1: (i=0, swapping smallest in {x[0],…,x[n-1]} with x[0])
4 2 1 3 smallest so far = x[0]
4 2 1 3 compare x[0] and x[1]
4 2 1 3 smallest so far = x[1]
4 2 1 3 compare x[1] and x[2]
4 2 1 3 smallest so far = x[2]
4 2 1 3 compare x[2] and x[3]
4 2 1 3 smallest is x[2]
4 2 1 3 swap x[0] and smallest (x[2])
1 2 4 3 end of pass 1
Pass 2: (i=1, swapping smallest in {x[1],…,x[n-1]} with x[1])
1 2 4 3 smallest so far = x[1]
1 2 4 3 compare x[1] and x[2]
1 2 4 3 compare x[1] and x[3]
1 2 4 3 smallest is x[1]
1 2 4 3 swap x[1] with smallest (x[1])
(No effect, but count the swap)
1 2 4 3 end of pass 2
Pass 3: (i=2, swapping smallest in {x[2],…,x[n-1]} with x[2])
1 2 4 3 smallest so far = x[2]
1 2 4 3 compare x[2] and x[3]
1 2 4 3 smallest so far = x[3]
1 2 4 3 swap x[2] and smallest (x[3])
1 2 3 4
Note: No need for last pass (singleton is sorted!)
SORTED in 9 operations:
3 Swaps + 6 Comparisons

5. Insertionsort: Repeatedly insert next element

a. Algorithm:
For each index i from 1 to (n-1):
Insert x[i] into the sorted list to its left.
Do this by repeatedly swapping it down to its sorted location.
Notice that before pass k, the leftmost k elements are sorted!

b. Example:
Original:
4 2 1 3 unsorted array x[]
Pass 1: (i=1, inserting x[1] to its left)
4 2 1 3 compare x[0] and x[1]
2 4 1 3 swap them!
2 4 1 3 end of pass 1
Pass 2: (i=2, inserting x[2] to its left)
2 4 1 3 compare x[1] and x[2]
2 1 4 3 swap them!
2 1 4 3 compare x[0] and x[1]
1 2 4 3 swap them!
1 2 4 3 end of pass 2
Pass 3: (i=3, inserting x[3] to its left)
1 2 4 3 compare x[2] and x[3]
1 2 3 4 swap them!
1 2 3 4 compare x[1] and x[2]
SORTED in 9 operations:
4 Swaps + 5 Comparisons

6. Bubblesort vs. Selectionsort vs. Insertionsort
Bubble Selection Insertion
Original: 4 2 1 3 4 2 1 3 4 2 1 3
Pass 1: 2 1 3 4 1 2 4 3 2 4 1 3
Pass 2: 1 2 3 4 1 2 4 3 1 2 4 3
Pass 3: 1 2 3 4 1 2 3 4 1 2 3 4

7. David Eck’s xSortLab Applet

a. http://math.hws.edu/TMCM/java/xSortLab/

b. Study this!

c. Note: he uses the improved bubblesort

d. Note: his selectionsort finds the max on each pass (simple variation)

e. Note: counts comparisons and copies (into temp variables), not swaps
Q: A swap would contribute how many copies?

8. A Clear, Concise (and Sometimes Useful) 4-Line Sort
(A Variant of Insertionsort)
import java.util.*;
import static java.lang.System.out;
class Foo {
public static void swap(int[] x, int i, int j) {
int temp = x[i];
x[i] = x[j];
x[j] = temp;
}

public static void sort(int[] x) {
for (int i=1; i<x.length; i++)
for (int j=0; j<i; j++)
if (x[i] < x[j])
swap(x,i,j);
}

public static void main(String[] args) {
int[] x = { 5, 2, 4, 1, 3 };
sort(x);
out.println(Arrays.toString(x)); // [1, 2, 3, 4, 5]!
}
}

9. A Confusing, Concise (and Never Useful) 3-Line Sort
(A Variant of the Variant of Insertionsort)
for (int k=x.length; k<x.length*x.length; k++)
if (x[k / x.length] < x[k % x.length])
swap(x,k / x.length,k % x.length);

10. Comparable: How to Sort a List of Strings (or other Objects)

a. “<” is only defined for numeric types.

b. For example: if ("foo" < "bar") … will not compile

c. So: How do we rewrite our 4-line sort to work with Strings?

d. Answer: Comparable Interface, with exactly one method:
int compareTo(T o)
Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

11.A 4-Line Sort Over Comparables:
import java.util.*;
import static java.lang.System.out;
@SuppressWarnings(value={"unchecked"})
class Foo {
public static void swap(Comparable[] x, int i, int j) {
Comparable temp = x[i];
x[i] = x[j];
x[j] = temp;
}

public static void sort(Comparable[] x) {
for (int i=1; i<x.length; i++)
for (int j=0; j<i; j++)
if (x[i].compareTo(x[j]) < 0)
swap(x,i,j);
}

public static void main(String[] args) {
String[] x = { "ab", "a", "z", "aa" };
sort(x);
out.println(Arrays.toString(x)); // [a, aa, ab, z]!
}
}

12. Making Your Own Comparable Class (and this-n-that)
import java.util.*;
import static java.lang.System.out;
@SuppressWarnings(value={"unchecked"})
class MyPoint implements Comparable {
private int x, y;
public MyPoint(int x, int y) { this.x = x; this.y = y; }
public String toString() { return "("+x+","+y+")"; }
public int compareTo(Object obj) {
// sorts by x first, then y second
// rename obj "that" so we can compare "this" and "that"
MyPoint that = (MyPoint) obj;
if (this.x != that.x)
return this.x - that.x;
else
return this.y - that.y;
}
}

@SuppressWarnings(value={"unchecked"})
class Foo {
public static void swap(Comparable[] x, int i, int j) {
Comparable temp = x[i];
x[i] = x[j];
x[j] = temp;
}

public static void sort(Comparable[] x) {
for (int i=1; i<x.length; i++)
for (int j=0; j<i; j++)
if (x[i].compareTo(x[j]) < 0)
swap(x,i,j);
}

public static void main(String[] args) {
MyPoint[] x = { new MyPoint(2,2), new MyPoint(2,1),
new MyPoint(3,1), new MyPoint(1,3) };
sort(x);
out.println(Arrays.toString(x)); // [(1,3), (2,1), (2,2), (3,1)]
}
}

13. Built-in Sorts: Arrays.sort and Collections.sort

a. Fast, space-efficient, error-free, and (best of all) already written for you! J

i. Q: So why write your own sorts?

ii. A: Don’t!!!! Except in an algorithms course, of course!!!

b. To sort an array:
int[] x = { 5, 2, 4, 1, 3 };
Arrays.sort(x);

c. To sort an ArrayList (or any other Collection):
ArrayList x = new ArrayList();
list.add("foo");
list.add("bar");
Collections.sort(x);

d. Works with your custom comparables, too!
@SuppressWarnings(value={"unchecked"})
class Foo {
public static void main(String[] args) {
MyPoint[] x = { new MyPoint(2,2), new MyPoint(2,1),
new MyPoint(3,1), new MyPoint(1,3) };
Arrays.sort(x);
out.println(Arrays.toString(x)); // [(1,3), (2,1), (2,2), (3,1)]
}
}

14. Comparator: Sorting Non-Comparable Classes (like java.awt.Point)
import java.util.*;
import java.awt.Point;
import static java.lang.System.out;
@SuppressWarnings(value={"unchecked"})
class Foo {
public static void main(String[] args) {
Point[] x = { new Point(2,2), new Point(2,1),
new Point(3,1), new Point(1,3) };
Comparator pointSorter = new Comparator() {
public int compare(Object obj1, Object obj2) {
Point p1 = (Point) obj1;
Point p2 = (Point) obj2;
if (p1.getX() != p2.getX())
return (int)(p1.getX() - p2.getX());
else
return (int)(p1.getY() - p2.getY());
}
};
Arrays.sort(x,pointSorter);
out.println(Arrays.toString(x)); // [(1,3), (2,1), (2,2), (3,1)]
}
}

15. Comparator: Sorting Comparable Classes in Non-Standard Ways
Example: Sort a list of numbers in absolute value order!
import java.util.*;
import java.awt.Point;
import static java.lang.System.out;
@SuppressWarnings(value={"unchecked"})
class Foo {
public static void main(String[] args) {
Integer[] x = { 2, 1, -1, 0, -2 };

Comparator absValSorter = new Comparator() {
public int compare(Object obj1, Object obj2) {
Integer i1 = (Integer) obj1;
Integer i2 = (Integer) obj2;
if (Math.abs(i1) != Math.abs(i2))
return Math.abs(i1) - Math.abs(i2);
else
// this way, for example, -2 comes before +2
return i1 - i2;
}
};

Arrays.sort(x);
out.println(Arrays.toString(x)); // [-2, -1, 0, 1, 2]

Arrays.sort(x,absValSorter);
out.println(Arrays.toString(x)); // [0, -1, 1, -2, 2]
}
}