1. The main idea of Bubble Sort:

Answer: Start by comparing the first pair of elements and swap them if the first element is greater than the second (assuming ascending order). Repeat for all pairs in the list. Repeat this whole iteration n-1 times (or until the whole list is sorted by checking if no swaps were done in the current iteration (optimisation 1)). There is no need to check the elements that were already sorted in subsequent iterations so reduce the range by 1 in each iteration (optimisation 2).

Feedback:

Alt answer #1:

Add the statement

Bubble sort is a sorting algorithm whose main idea is to place the largest unsorted element into its final position after each traversal.

2. What is the largest number of swaps performed by Bubble Sort per item in the list?

Answer:

It is n-1 swaps! 🙂

Feedback: Would be good to define what n actually is

Alternate Answer:
n-1 swaps, where n is the number of elements in the list

Yeap this is correct

3. What is the best case and worst case complexity?

Answer:

The overall complexity of Bubble sort 1 in both best and worst cases is O(n^2)

The overall best-case complexity of Bubble sort 2 is O(n) and its worst case complexity is O(n^2) where n is the length of the list.

Feedback: Would be good to define what n actually is for Bubble Sort 1:

The overall complexity of Bubble sort 1 in both best and worst cases is O(n^2), where n is the number of elements in the list

4. Explain why the best and worst cases are as stated. No explanation no marks.

Answer:

Bubble sort 1 has two loops. The outer loop runs n-1 times and so does the inner loop (n is the length of the list). So the overall complexity in all cases comes out to be (n-1)^2 which is O(n^2).

Bubble sort 2 also has two loops but there is a conditional break. If none of the numbers are swapped during a traversal, then the loop is stopped. The best case of O(n) occurs when the list is already sorted and it takes one traversal to make sure that the list is sorted. 

The worst case is when the list is sorted in the reverse order (both inner and outer loop will run n-1 times). So the worst case complexity is O(n^2).

Alternative Answer #1 (more in depth)
(Feedback: Correct)

• For the best case, this will occur when the list is already sorted
  • Bubble Sort II will check every element in the list once, resulting in n operations, where  n  is the number of elements in the list.
  • It will check only once since the “swapped” value will be true after one traversal of the list, making the algorithm exit early.
  • This gives a time complexity of O(n), where n  is the number of elements in the list
• For the worst case, this will occur when the list is in  reverse order
  • The “swapped” variable will not break early.
  • The number of comparisons will be (n-1) + (n-2) + … + 1, which simplifies to (n^2-n)/2, which results in O(n^2), where n  is the number of elements in the list

Alternative Answer #2 (correction of alt answer #1)

• For the best case, this will occur when the list is already sorted
  • Bubble Sort II will check every element in the list once, resulting in n operations, where  n  is the number of elements in the list.
  • It will check only once since the “swapped” value will be true after one traversal of the list, making the algorithm exiting early.

Swapped variable is initialised to False, and after one iteration, if there is a swap, the swapped value will be True. However, if there is an iteration where the swapped value remains as the Boolean value False, the iteration stops.