Homework 1, The Bubble Sort.
Short Description:
Perform an "analysis" of the bubble sort.
Goals
When you finish this homework, you should have:
- Traced bubble sort.
- Described bubble sort at a high level.
- Argued that bubble sort is correct.
- Performed a worst case asymptotic analysis of bubble sort.
Formal Description
Consider bubble sort
BUBBLE-SORT(A)
- for i = 1 to A.length-1
- for j = A.length downto i+1
- if A[j] < A[j-1]
- swap(A[j], A[j-1])
Perform the following:
- Trace bubble sort.
- Describe bubble sort at a high level.
- 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]
- 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.