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.