SUNY Geneseo Department of Computer Science

Correctness of Bubble Sort in Lists

Previous Lecture

Misc

CS Dept. Halloween party

• Tomorrow (Friday), 4:00 PM
• South 309

Hand out Lab 8

Questions?

Homework

• All tile colors can be handled in one method
• Black tiles?

• Coming back? Postconditions

Recursive Bubblesort

Goal: A "SortableList" subclass that handles a "sort" message that makes a list put its elements in ascending order. Assume elements are all ones for which "<" is meaningful.

Strategy: Move the smallest element in the list to the front, by swapping small elements with things in front of them, then recursively sort the tail of the list

    // In class SortableList, a subclass of List...
    void sort() {
        if ! this.isEmpty()
            this.bringSmallestToFront()
            this.getRest().sort()
    }

    void bringSmallestToFront()
        // Postcondition: smallest element in
        //   list is at head
        // Precondition: list is not empty
        if ( this.getRest().isEmpty() )
            do nothing
        else
            this.getRest().bringSmallestToFront()
            if this.getFirst() < this.getRest().getFirst()
                do nothing
            else
                first = this.getAndRemove()
                second = this.getAndRemove()
                this.addItem( first )
                this.addItem( second )

Mini-assignment: build the swapping from primitive list messages

• How to swap?

Correctness?

• Start with sort
• Use induction on length of list
• Or maybe bringSmallestToFront, since sort uses it
• Or assume bringSmallestToFront is correct, use that to prove sort, then prove bringSmallestToFront
• Theorem used to prove another theorem = lemma
• sort is correct because...
  • Base case, 0 elements in list
    • "! this .isEmpty" fails, algorithm does nothing
    • And list is still vacuously in order
  • Assume sort correctly sorts a list of length = k-1 >= 0
  • When sorting a list of length k
    • "! this.isEmpty()" succeeds
    • Brings smallest element to head (by lemma, list isn't empty)
    • this.getRest().sort() is working on list of k-1 elements, which by induction hypothesis it sorts correctly
    • So now smallest element is first and all larger elements are later, and those later elements are sorted
    • i.e., whole list is sorted
• bringSmallestToFront
  • Base case, list of 1 element
    • 1st "if"" succeeds, algorithm does nothing
  • Induction hypothesis: assume bringSmallestToFront brings smallest item to front of length k-1 >= 1 list
  • Show bringSmallestToFront brings smallest item in length k >= 2 list to front
    • Since k >= 2 1st "if" fails
    • this.getRest() returns tail of list, of length k-1
    • So this.getRest().bringSmallestToFront brings smallest item in tail to front of tail
    • 2 cases:
      • Head < smallest item in tail
        • Head is therefore smallest in list, nothing needs to be done, nothing is
      • Head (F) >= smallest item in tail (S)
        • Algorithm goes to "else", takes out two front items, call them "F" and "S", replaces them into list with F after S in final list
        • S, now at head, is smaller than F, and is also smallest of all other items, i.e., smallest in whole list, now at front

Execution Time?

• Count simple list messages
• Also need to know about time for bringSmallestToFront
• Recurrence for bringSmallestToFront
  • Mini-assignment
• Then plug answer to bringSmallestToFront into recurrence for sort

Next Lecture