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…

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.

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

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  

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…