SUNY Geneseo Department of Computer Science

Performance Analysis for List Bubble Sort

Previous Lecture

Misc

Exam 2 is next Tuesday, Nov. 9

• Mainly lists, their algorithms, and analyses
• Maybe a little bit on stacks (this Thursday's topic)
• Same rules and format as 1st exam

Questions?

Faster robots? See "setSpeed"

Some browsers put blank lines at front of world files

Proof for homework

• Induction on number of tiles in hunt
• Case analysis according to tile color

Recursive Bubblesort

    // In class SortableList, a subclass of List...
    void sort() {
        if ! this.isEmpty()
            this.bringSmallestToFront()
            this.getRest().sort()
    }
    void bringSmallestToFront()
        if ( ! this.getRest().isEmpty() )
            this.getRest().bringSmallestToFront()
            if this.getFirst() > this.getRest().getFirst()
                first = this.getAndRemove()
                second = this.getAndRemove()
                this.addItem( first )
                this.addItem( second )

Execution Time?

Count simple list messages

Also need time for bringSmallestToFront, plug it into recurrence for sort

Recurrence for bringSmallestToFront

• Mini-assignment
• Recurrence
  • f(n) = 2 if n = 1
  • f(n) = 6 + f(n-1) if n > 1, best case
    • First item already smallest
  • f(n) = 10 + f(n-1) if n>1, worst case
    • First item not smallest
• Closed form, best case
  • f(n) = 6n + 2 ?
  • Or maybe 6(n-1) + 2 ?
• Proof by induction on n
  • Base case, n = 1
    • f(n) = 2 from recurence
    • = 6(1-1) + 2
  • Induction hypothesis, assume f(k-1) = 6(k-1-1) + 2 = 6(k-2) + 2
  • Show f(k) = 6(k-1) + 2
    • f(k) = 6 + f(k-1) f/ recurrence
    • = 6 + 6(k-2) + 2
    • = 6 + 6k - 12 + 2
    • = 6k - 4
    • = 6(k-1) + 2
• Worst case
  • f(n) = 10n + 2 ?
  • Or 10(n-1) + 2 ?
  • Proof left to the listener
• bringSmallestToFront, n-item list:
  • Best case: 6n - 4 messages
  • Worst case: 10n - 8

What about sort?

• Recurence relation for worst case
  • f(n) = 1 if n = 0
  • f(n) = 2 +10n - 8 + f(n-1) if n > 0
  • = 10n - 6 + f(n-1) if n > 0

• Multiples of ten (+ 4), added together
  • (Implies summation)
• Rules for simplifying summations
  • See chapter 9

• 5n² - n + 1 list messages, wanted time
• Roughly proportional to n²
• Or Θ(n²)
  • (vs Θ(n logn ) for better sorts)

Next

Stacks, a list-like data structure

Read

• Intro to Chapter 12 (page 391)
• Section 12.2 through 12.2.5

Next Lecture