Java程序辅导

Monday 5/9
Announcements:
 Homework 12 due Friday, 5/13
 Quiz 5 Wednesday or Friday (Heaps, Sets, Maps, Hashing)
 Lab 10 due next Monday, 5/16
For Next Time
 Review Sections 8.1 and 8.2 – Sorting
 Read Section 8.3 Insertion Sort
Today
 Lab 10 Overview and design
 Review In-class Exercise 13-Hashing
 In-class Exercise 14-TreeMapHashMap – Programming
 Java Sorting Algorithms
Evil Guess Word
 Design
 Helper class(es) – Dictionary / Words (fields [data structures], methods)
 Evil Guess Word class with main (variables, data structures, methods)
 main method
 Create Helper class object and read the dictionary – should only read 
the file once – what data structure will you use to store the words?
 Loop while user wants to play
• Get legal word length
• Get legal number of guesses
• Ask user if they want to see remaining word list information (debug)
• Loop while guesses are left and word not guessed
– display (pattern, used letters, guesses, debugging info …)
– get legal letter
– set data fields in main and Helper class(es)
– check win or lose
• prompt to play again
call a legal length method to 
determine if the length is legal
What data structure will you 
use to find the new current word 
list?
Use the small-dictionary while testing and programming
Performance of Hash Tables
 Load factor is the number of entries, n, divided by the table 
size (L = n/table.length)
 Open addressing with linear probing
 Expected number comparisons needed for a successful 
search  :  c ≈ ½(1+ 1/(1-L))
 Expected number of comparisons for an unsuccessful 
search: c ≈ ½(1+ 1/(1-L)2)
 Chaining 
 Expected number comparisons needed for a successful 
search: c  ≈  1+L/2
 Expected number of comparisons for an unsuccessful 
search: c ≈ L
5Search / Insert / Remove
Data Type
Search 
Worst
Search 
Average
Insert
Worst
Insert
Average
Remove 
Worst
Remove 
Average
Unordered
ArrayList
O(n) O(n) O(n) O(1) O(n) O(n)
Ordered
ArrayList
O(log n) O(log n) O(n) O(n) O(n) O(n)
Unordered
LinkedList
O(n) O(n) O(1) O(1) O(n) O(n)
BST O(n) O(log n) O(n) O(log n) O(n) O(log n)
Balanced
Tree
O(log n) O(log n) O(log n) O(log n) O(log n) O(log n)
Hashing O(n) O(1) O(n) O(1) O(n) O(1)
In-class Exercises
15-OpenHashingChaining
Questions?
14-TreeMapHashMap
Lab 10
Standard Sorting Methods in Java API
 Java API provides a class Arrays with several overloaded sort
methods for different array types
 The Collections class provides similar sorting methods for 
Collections (e.g., ArrayList, LinkedList)
 Sorting methods for arrays of primitive types are based on 
quicksort algorithm
 Sorting for arrays of objects and Lists based on mergesort
Java Sorting Methods
Arrays Class static methods
Collections Class static methods
 Arrays.copyOf(array, array.length)
 Arrays.sort(array) //sort using compareTo
 Arrays.sort(array, comp) //sort using compare
 Arrays.toString(array)
 Collections.sort(list) //sort using compareTo
 Collections.sort(list, comp) //sort using compare
 Collections.copy(destList, srcList)  //destList.size() >= srcList.size();
 Collections.addAll (col, “Barb”, “Mary”, “Liz”,  “Janet”) ;
Sorting Strings
 Create a String array, 
String[] a = {“1234”, “89”,  …};
 Sort using Arrays class
Arrays.sort(a);            //sort array a
System.out.println(Arrays.toString(a));
 Create CompareByLength class
 Sort using Arrays class with Comparator
Arrays.sort(a, compByLength);
Comparator
 Allows us to compare objects using ordering that is 
different from the “natural ordering” compareTo(E o)
 Example: Want to compare Strings using length first 
dictionary ordering second
 “Natural Ordering” : Dictionary ordering
• “9”.compareTo(“123”) is positive (“9”>”123”)
Need a way to compare Strings using length first
• Create a new class CompareByLength that 
implements Comparator
Class CompareByLength
public class CompareByLength
implements Comparator  {
public int compare (String s1, String s2){
if (s1.length() != s2.length())
return (s1.lenght() – s2.length());
else
return s1.compareTo(s2);
}//compare
}//class
Using a Comparator
Client Code
String s1 = “9”, s2=“123”
CompareByLength comp = 
new CompareByLength ();
If ( comp.compare(s1,s2)<0 )
System.out.println(“s1 is smaller than s2”);
14
Sorting Algorithms
 Basic Sorts
 Selection sort 
 Insertion sort
Bubble sort
 Shell sort
 Faster Sorts
Mergesort
Heapsort
Quicksort
 How fast can you sort n elements?
Optimal algorithms
 Better than optimal (if time permits)
Radix Sort
Counting Sort
Comparing Algorithms
 Time needed to sort n elements
WorstTime(n)
BestTime(n)
AverageTime(n)
 Space needed
In-place sort
 Relative ordering
Stable  sort
Simple Sorts
 Selection Sort
 Insertion Sort
 https://www.toptal.com/developers/sorting-algorithms
 Running time
best case
worst case
 average case
 In-place?
 Stable?
In-class exercise on sorting