SUNY Geneseo Department of Computer Science

Execution Time of Bubble Sort

Previous Lecture

Questions?

Execution times for lab?

• Count operations representative of work/time

Algorithm Design and Analysis Example

Problem: sort a list

Bubble Sort

    // In a SortableList subclass of List...
    sort()
        if ( ! this.isEmpty() )
            this.findSmallestAndPutAtFront()
            this.getRest().sort()
			
    findSmallestAndPutAtFront()
        if ! this.isEmpty() && ! this.getRest().isEmpty()
            this.getRest().findSmallestAndPutAtFront()
            if this.getRest().first() < this.first()
                temp = this.getAndRemove()
                this.getRest().addItem( temp )

How fast is bubble sort, in terms of list length, n?

• Guess: Θ(n²)
  • Sort is Θ(n),
  • Done Θ(n) times,
  • Total looks like Θ(n²)
• Careful derivation
  • Start w/ sort
  • Recurrence, count list operations
    • s(n) = 1 if n = 0
    • s(n) = 2 + f(n) + s(n-1) if n > 0
  • Where f = number of list messages findSmallestAndPutAtFront sends on an n-item list (worst case)
    • f(n) = 3 if n <= 1
    • f(n) = 10 + f(n-1) if n > 1
  • Find closed form
    • 10n + 3 if base case were 0 (kn+c)
    • But 0 is special case, use 1 as base case, guess 10(n-1) + 3 = 10n - 7
  • Proof f(n) = 10n - 7
    • Induction on n
    • Base case, n = 1
      • f(n) = 3 f/ recurrence
      • = 10 * 1 - 7
    • Induction hypothesis: assume f(k-1) = 10(k-1) - 7
    • Show f(k) = 10k - 7
      • f(k) = 10 + f(k-1) f/ recurrence
      • = 10 + 10(k-1) - 7
      • = 10 + 10k -17
      • = 10k - 7
  • Revised recurrence for s
    • s(n) = 1 if n = 0
    • s(n) = 2 + 10n - 7 + s(n-1) if n > 0
    • = 10n - 5 + s(n-1) if n > 0
• Mini-assignment: look for pattern, and phrase in English
  • Hint: don't do all arithmetic

Next Lecture