SUNY Geneseo Department of Computer Science

Designing and Analyzing Bubble Sort, Part 2

Previous Lecture

Misc

Hand out Lab 9

Hand out Homework 1

Questions?

How to bubble smallest item to front of list instead of largest to end in "findSmallestAndPutAtFront?"

• Depends on relative order of compare-and-swap and recursion

Algorithm Design and Analysis Example

Problem: sort a list

(Precondition: all items in the list are comparable using "<", ">")

Solution idea: "bubble sort"

• "Bubble" smallest value to front of list by swapping it with its predecessor whenever predecessor is smaller
• Then sort the tail of the list in the same way

    // In a SortableList subclass of List...
    sort()
        if ( ! this.isEmpty() )
            this.findSmallestAndPutAtFront()
                //postcondition: smallest item in list is at head
            this.getRest().sort()

    findSmallestAndPutAtFront()
        if ! this.isEmpty() && ! this.getRest().isEmpty()
            this.getRest().findSmallestAndPutAtFront()
            if this.getRest().first() < this.first()
                temp = this.getAndRemove()
                this.addItem( this.getAndRemove() )
                this.getRest().addItem( temp )

(Notice that the 2nd line of the swap code above turns out to be unnecessary -- the first "getAndRemove" also makes the original second item first)

Be careful about the list operations you use to swap...

Correctness of findSmallestAndPutAtFront

• If the list has at least 2 elements...
  • Recursive findSmallestAndPutAtFront brings smallest item in tail to 2nd place in list,
  • Smallest overall is then either head or 2nd,
  • Swap if 2nd is less thus puts smallest overall in head
• If list has 0 or 1 elements...
  • Smallest is necessarily at front, vacuously (0 elements) or trivially (only 1 element)

In Java, (most) objects handle...

        a.compareTo( b )

• Return negative int if a < b
• Return 0 if a == b
• Return positive if a > b

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

• Mini-assignment - see what you can say about this

Next Lecture