Homework 1, The Bubble Sort.

Short Description:

Perform an "analysis" of the bubble sort.

Goals

When you finish this homework, you should have:

Formal Description

Consider bubble sort
BUBBLE-SORT(A)
  1. for i = 1 to A.length-1
  2. for j = A.length downto i+1
  3. if A[j] < A[j-1]
  4. swap(A[j], A[j-1])
Perform the following:
  1. Trace bubble sort.
  2. Describe bubble sort at a high level.
  3. Argue that bubble sort is correct.
    • State a loop invariant for lines 2-4 and argue this loop invariant holds.
    • State a loop invariant for lines 1-4 and argue this loop invariant holds.
    • Use the above to argue that the algorithm will terminate with the condition: A[1] ≤ A[2] ≤ ... ≤ A[n]
  4. Perform a worst case asymptotic analysis of bubble sort.

Notes

Please note that this is a different variation of bubble sort than found elsewhere, please be careful using other sources.

Required Files

A single document containing your work and answers.

Submission

Submit the assignment to the D2L folder Homework 1 by the due date.