Transcript A Skill Is Born: The Emergence of Web Site Design Skills (1994

Foundations of Software Design
Fall 2002
Marti Hearst
Lecture 21: Sorting, cont.
1
QuickSort
• A Divide-and-Conquer recursive algorithm
• Divide:
– If only one item in list, return it.
– Else choose a pivot, and
– Divide the list into 3 subsets
• Items < pivot, pivot, items > pivot
• Recurse:
– Recursively solve the problem on the subsets
• Conquer:
– Merge the solutions for the subproblems
• Concatenate the three lists
2
Partitioning in QuickSort
• Partition:
– Select a key (called the Pivot) from the dataset
– Divide the data into two groups such that:
• All the keys less than the pivot are in one group
• All the keys greater than the pivot are in the other
– Note: the two groups are NOT required to be sorted
• Thus the data is not sorted, but is “more sorted” than
before
• Not too much more work to get them sorted.
– What is the order of this operation?
• Linear (or O(n))
3
QuickSort
• An advantage: can be done “in place”
– Meaning you don’t need to allocate an additional array or
vector to hold the temporary results
• Do the in-place swapping in the divide step
– Choose pivot
– Have two indexes: L and R
– While L is < R
• Move L forwards until A[L] > pivot
• Move R backwards until A[R] < pivot
• Swap them
4
The QuickSort Recursive Step
public void quickSort(int left, int right) {
if (left > right)
return;
int partition = partitionArray(left, right);
quickSort(left, partition – 1);
quickSort(partition + 1, right);
}
}
5
Partitioning in QuickSort
public int partitionArray(int left, int right) {
int pivot = a[left];
while (left < right) {
while (a[left] < pivot)
left++;
while (a[right] > pivot)
right--;
swap(left, right);
}
return left;
}
6
Other Methods
public class QuickSort {
private int a[];
QuickSort (int size) {
Random r = new Random();
int range = 1000;
a = new int[size];
for (int i=0;i<size;i++) {
a[i] = r.nextInt(range);
}
}
public void printQuickSort() {
for (int i=0; i<a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
7
Other Methods
private void swap (int l, int r) {
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
public static void main(String args[]){
QuickSort qs = new QuickSort(8);
System.out.println("Before Quicksort: ");
qs.printQuickSort();
qs.quickSort(0, qs.a.length-1);
System.out.println("After Quicksort: ");
qs.printQuickSort();
}
8
Output
Before Quicksort:
594 344 349 690 830 557 726 612
After Quicksort:
344 349 557 594 612 690 726 830
Before Quicksort:
840 455 729 485 751 661 806 170
After Quicksort:
170 455 485 661 729 751 806 840
Before Quicksort:
432 424 815 968 637 925 880 878
After Quicksort:
424 432 637 815 878 880 925 968
9
Quick Sort – Choosing the Pivot
• Alternative Strategies
– Choose it randomly
• Can show the expected running time is O(n log n)
– Sample from the set of items, choose the median
• Takes more time
• If sample is small, only a constant overhead
10
Quick Sort
• Running Time analysis
– If the pivot is always the median value
•
•
•
•
Each list is divided neatly in half
The height of the sorting tree is O(log n)
Each level takes O(n) for the divide step
O(n log n)
– If the list is in increasing order and the pivot is the last
value
• Each list ends up with one element on the right and all the
other elements on the left
• The height of the sorting tree is O(n)
• Each level takes O(n) for the divide step
• O(n^2)
– However, in practice (and in the general case), QuickSort
is usually the fastest sorting algorithm.
11
QuickSort vs. MergeSort
• Similarities
– Divide array into two roughly equal-sized groups
– Sorts the two groups by recursive calls
– Combines the results into a sorted array
• The difficult step
– Merge sort: the merging
– Quick sort: the dividing
• Running Time
– QuickSort has a bad worst case running time
– But in practice it is faster than the others
• Constants, and the way data is distributed
– Also, MergeSort requires an additional array
12
Algorithm Animations
– http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html
13
Bucket Sort
• Sorting takes at least O(n log n)
• Can go faster given certain restrictions
– Restriction: you know all the keys fall in some range
1…M
– Make an array of size M
– For each item with key k, put it in bucket A[k]
– The array then holds results in sorted order
• Takes time O(n + M) and space O(M)
• Doesn’t work if you don’t know the range of keys in
advance
– How is this different than a hash table?
14
Radix Sort
• Combine:
– Bucket sort idea
– Stable sort idea
– Binary representation for the key
• To do the sort
– Divide: Sort on bit position n into 2 buckets
– Recurse:
• For each bucket:
• Sort on bit position n-1 into 2 buckets
• Running time:
– O (b * n) where b == length of the key
15
Slide adapted from Goodrich & Tamassia
16
Sorting Arbitrary Objects
• We want to write sorting algorithms so they
can sort lists of objects of any type
• To do this, we use java interfaces
• To discuss this, we first review
– Polymorphism
– Inheritance
– Abstract Classes
17
Inheritance
• Models the IS-A relationship
–
–
–
–
a student is-a person
an undergraduate is-a student
a rectangle is-a shape
a rook is-a piece
• Contrast with the Has-A relationship
– a student has-a name
– a rook has-a position
• Is-a relationships indicate inheritance, has-a
relationships indicate composition (fields)
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
18
Inheriting from a Class
• A class inherits another class of it contains the
extends keyword
public class Student extends Person
• Person is said to be
–
–
–
–
the parent class of Student
the super class of Student
the base class of Student
an ancestor of Student
• Student is said to be
–
–
–
–
a
a
a
a
child class of Person
sub class of Person
derived class of Person
descendant of Person
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
19
Inheriting from a Class
• If a class header does not include the extends clause
the class extends the Object class by default
public class Die
– Object is an ancestor to all classes
– it is the only class that does not extend some other class
• A class extends exactly one other class
– extending two or more classes is multiple inheritance. Java
does not support this directly, rather it uses Interfaces.
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
20
Implications of Inheritance
• The subclass gains all of the behavior (methods)
and data regarding state (instance variables) of the
super class and all ancestor classes
• Subclasses can:
– add new fields
– add new methods
– override existing methods (change behavior)
• Subclasses may not
– remove fields
– remove methods
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
21
Access Modifiers and Inheritance
• public
– accessible to all classes
• private
– accessible only within that class. Hidden from all sub
classes.
• protected
– accessible by classes within the same package and all
sub classes
• Instance variables should usually be private
• protected methods are used to allow subclasses to
modify instance variables in ways other classes can't
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
22
The Object Class
• All classes inherit Object directly or indirectly
(via a chain of inheritance)
• Minimal class, but it does contain the
toString, equals and getClass methods
– implication is every class has a toString and equals
method
– normally classes will override these methods to give
them a more meaningful behavior than the ones
Object provides
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
23
Shape Classes
• Declare a class called ClosedShape
– assume all shapes have x and y coordinates
– override Object's version of toString
• Possible subclasses of ClosedShape
–
–
–
–
Rectangle
Circle
Ellipse
Square
• Possible hierarchy
ClosedShape -> Rectangle -> Square
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
24
A Shape class
public class Shape
{ private double myX;
private double myY;
public Shape()
{
this(0,0);
}
public Shape (double x, double y)
{ myX = x;
myY = y;
}
public String toString()
{
return "x: " + x + " y: " + y;
}
}
Slide adapted
Michael Scott,
//fromOther
methods not shown
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
25
Overriding methods
• Any method that is not final may be
overridden in a descendant class
• May use the original method if it is only a
partial change:
• The Rectangle class
– adds data, overrides toString
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
26
A Rectangle Class
public class Rectangle extends Shape
{ private double myWidth;
private double myHeight;
public Rectangle()
{ this(0, 0);
}
public Rectangle(double width, double height)
{ myWidth = width;
myHeight = height;
}
public String toString()
{ return super.toString() + " width " + myWidth
+ " height " + myHeight;
}
}
// other methods not shown
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
27
The Keyword super
• super is used to access something from the
super class that has been overridden
• Rectangle's toString makes use of the toString in
Shape by calling super.toString()
– without the super calling toString would result in infinite
recursive calls
• Java does not allow nested supers
super.super.toString()
results in a syntax error even though technically
this refers to a valid method, Object's toString
• Rectangle partially overrides Shape’s toString
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
28
The role of final in Inheritance
• A class may be declared as final
– that class may not be extended
• A method in a class may be declared as final
– that method may not be overridden
– guarantees behavior in all descendants
– can speed up a program by allowing static binding
(binding or determination at compile time what code will
actually be executed)
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
29
Constructors and Inheritance
• Constructors handle initialization of objects
• When creating an object with one or more
ancestors (every type except Object) a chain of
constructor calls takes place
• The reserved word super may be used in a
constructor to call a one of the parent's
constructors
– must be first line of constructor
• if no parent constructor is explicitly called the
default, 0 parameter constructor of the parent
is called
– if no default constructor exists a syntax error results
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
30
Initialization method
public class Rectangle extends Shape
{ private double myWidth;
private double myHeight;
public Rectangle()
{ init(0, 0);
}
public Rectangle(double width, double height)
{ init(width, height);
}
public Rectangle(double x, double y,
double width, double height)
{ super(x, y);
init(width, height);
}
private void init(double width, double height)
{ myWidth = width;
myHeight = height;
}
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
31
Polymorphism and Object Variables
Rect r = new Rect(10, 20);
Shape s = r;
System.out.println("Area is " + s.getArea());
• The above code works if Rect extends Shape
• An object variable may point to an object of its
base type or a descendant in the inheritance
chain
– A Rect extends shape so s may point to it
• This is a form of polymorphism and is used
extensively in the Java Collection classes
– Vector, ArrayList are lists of Objects
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
32
More Polymorphism
Circle c = new Circle(5);
Rect r
= new Rect(5, 3);
Shape s = null;
if( Math.random(100) % 2 == 0 )
s = c;
else
s = r;
System.out.println( "Shape is "
+ s.toString() );
– code works because s is polymorphic
– method call determined at run time by dynamic binding
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
33
Type Compatibility
Rect r = new Rect(5, 10);
Shape s = r;
s.changeWidth(20); // syntax error
• Polymorphism allows s to point at a Rect object but there are
limitations
• The above code does not work
• Statically s is a shape
– no changeWidth method on shape
– must cast s to a rectangle;
Rect r = new Rect(5, 10);
Shape s = r;
(Rect)s.changeWidth(20); //Okay
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
34
Problems with Casting
• The following code compiles but an exception
is thrown at runtime
• Casting must be done carefully and correctly
• If unsure of what type object will be the
instanceof operator or the getClass()
method may be used
expression instanceof ClassName
Rect r
= new Rect(5, 10);
Circle c = new Circle(5);
Shape s = c;
((Rect)s).changeWidth(4);
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
35
Abstract Classes and Methods
• An abstract class is one that may not be
instantiated
– an object of that type never exists
– a Shape or a Mammal
• a method may be declared abstract in its
header, after visibility modifier
– no body to the method
– all derived classes must eventually implement this
method
– any class with 1 or more abstract methods is an
abstract class
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
36
Multiple Inheritance
• Inheritance models the "is-a" relationship
between real world things
• In the real world a thing can have "is-a"
relationships with several other things
– a Graduate Teaching Assistant is-a Graduate
Student. Graduate Teaching Assistant is-a Faculty
Member
– a Student is-a Person; a Student is a
SortableObject
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
37
The Power of Polymorphism
• Polymorphism
– allows collections, such as ArrayList, to hold anything
– allows a method to work on multiple types
• create a sorting method that accepts arrays of
SortableObjects
• it can sort anything
• Java chooses to use a limited form of multiple
inheritance
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
38
Interfaces
• A Java interface is a "pure abstract class".
Design only, no implementation.
• Interfaces are declared in a way similar to
classes but
– consist only of public abstract methods
– public final fields
• A Java class extends exactly one other class,
but can implement as many interfaces as
desired.
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
39
Why Use Interfaces?
• Useful for
– Capturing similarities among unrelated classes without
artificially forcing a class relationship.
– Declaring methods that one or more classes are expected to
implement.
– Revealing an object's programming interface without
revealing its class.
• You can use interface names anywhere you can use
any other data type name.
• Only an instance of a class that implements the
interface can be assigned to a reference variable
whose type is an interface name.
40
The Java Comparable Interface
• compareTo should return
– an int < 0 if the calling object is less than the
parameter,
– 0 if they are equal,
– an int > 0 if the calling object is greater than the
parameter
package java.lang
public interface Comparable
{
public int compareTo( Object other );
}
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
41
Implementing an Interface
public class Card implements Comparable
{
public int compareTo(Object otherObject)
{
Card other = (Card)otherObject;
return myValue - other.myValue;
}
}
• If a class declares that it will implement an interface,
but does not provide an implementation of all the
methods in that interface, that class must be abstract
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
42
Polymorphism Again
public static SelSort(Comparable[] list)
{ Comparable temp;
int small;
for(int i = 0; i < list.length - 1; i++)
{ small = i;
for(int j = i + 1; j < list.length; j++)
{ if( list[j].compareTo(list[small]) < 0)
small = j;
}
temp = list[i];
list[i] = list[small];
list[small] = list[i];
}
}
Slide adapted from Michael Scott,
http://www.cs.utexas.edu/users/scottm/oldClasses/cs307Spring02/syllabus.htm
43
Interfaces vs. Other Things
• An interface cannot implement any methods,
whereas an abstract class can.
• A class can implement many interfaces but can have
only one superclass.
• An interface is not part of the class hierarchy.
• Unrelated classes can implement the same interface.
44
A Drawback to Interfaces
Once you have defined an interface, you usually can't
change it because there will be a lot of code already
written that depends on it. This is because an object
has to implement all of the methods in an interface,
so you can't add more after the fact without breaking
everything that came before.
45
More Interfaces Info
• A short introduction to java interfaces
http://java.sun.com/docs/books/tutorial/java/concepts/interface.html
• The java tutorial on interfaces
http://java.sun.com/docs/books/tutorial/java/interpack/interfaces.html
46