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 slide
HanoiBAS.exe   QuickBasic executable (Microsoft operating system required) animating the Towers of Hanoi
HanoiBAS.bas   QuickBasic source code, if you want to examine it

Time 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.