BACK |
Algorithm Analysis |
NEXT |
Code from Sedgewick's Chapter 2 Code from Sedgewick's Chapter 6
PowerPoint presentations: Sahni's Lecture 2 Sahni's Lecture 3 Koffman&Wolfgang, Ch. 2 (slide 41ff) Locally maintained slide set.
LinkedSkeleton.java
Skeleton linked list code to allow experimenting with analysis of linked list
algorithms [txt]
TestListTraversal.java Specimen use.
[txt]
Summary across a number of programming patterns: Patterns.java [rtf] [txt] [exe] Output from execution
Code slides for projection:
Binary Search Selection
Sort Insertion Sort
Merge Sort [for inclusion in DemoSort]
Link to an animation demonstrating numerous sorting algorithms.
Full Java application exercising the sorts:
DemoSort.java
Handout (RTF format) .txt version
for browsing
uses
MyComparable.java
Handout (RTF format)
.txt version for browsing
Above application as a runnable JAR file:
DemoSort.jar
Above JAR file in a JSmooth wrapper :
DemoSort.exe
DemoSortRun.html Browsable specimen
execution with graph
Link to a discussion of Bubble Sort — a fossil algorithm from the early days of computing
Optimization of Insertion Sort — binary search for linear search, system utility for data movement
Towers of Hanoi example: Code slideTime Complexity Example: TimeComplexity.java [txt] Output from a run
Enrichment material — not subject to examination
Arrays_sort.txt Sun's code for java.util.Arrays.sort — as a single two-column page in RTF format — HTML copy of abbreviated code.
Code Elegance Example: the merge logic from java.util.Arrays.mergeSort()
// Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; }
Note that the first boolean expression (in front of the OR) copies over all the left side if the right side has been finished. The other side of the OR is two booleans ANDed together (since AND has higher precedence than OR). The left-hand one, if it is false (the left side has been finished), copies over all the right side. The final boolean has been guarded by the two previous expressions and selects the side if both sides have contents.