SUNY Geneseo Department of Computer Science

Algorithm Design and Analysis with Lists, Part 1

Previous Lecture

Misc

Hour exams are graded

Questions?

Concatenation exercise

    List list1
        ... initialized somehow....
    List list2
        ... initialized somehow ...
    List list3 = new List()
    list3.concat( list1.copy() )
    list3.concat( list2 )

Solution: explicitly make copies (as the code above does -- it started without the "list1.copy()")

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

An algorithm based on this idea....

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

• Mini-assignment: finish findSmallestAndPutAtFront()

Is it correct?

• If list is empty
  • Must be in order, 'cause no elements to be out of order
• Otherwise
  • "Find smallest..." puts smallest element at head of list,all items in tail are larger
  • Sorting tail puts those larger elements in order, hence whole list is in order
• Implicit induction

Next Lecture