1. Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted and….
2. In the Bubble sort (a comparison sort) the _____through the list is repeated until no swaps are needed, which indicates that the list is sorted.
3. Why is it called 'Bubble' sort?
4. The Bubble sort is quite simple to code, but too slow and impractical for most problems. Fill in the blanks..
5. Consider the steps below for a bubble sort algorithm. Can you fill in the blanks?
6. Bubble sort could be used to sort the following list: 3, 2, 4, 1, 5, in which case the first step in the first loop of the algorithm would give:
2, 3, 1, 4, 5 (4<5 so the two values are not swapped)
2, 3, 4, 1, 5 (2<3 so the two values are not swapped)
2, 3, 4, 1, 5 (1<4 so the two values are swapped)
5, 2, 4, 1, 5 (3<5 so the two values are swapped)
7. Complete the blanks after analysing the rest of the steps shown for the first loop (Bubble Sort)
2, 3, 4, 1, 5 (3<4 so the two values are not swapped)
2, 3, 4, 1, 5 (1<4 so the two values are swapped)
2, 3, 1, 4, 5 (4<5 so the two values are not swapped)
What comes next?
__________________________________________
1,2,3,4,5 (First pass completed)
1,3,2,4,5 (Second pass completed)
2, 3, 1, 4, 5 (First pass completed)
5,4,1,3,2 (Second Pass completed)
8. A Bubble sort will stop when the algorithm has completed a loop without having to swap anything and the list is in order.
9. List: [19, 1, 9, 7, 3, 10, 13, 15, 8, 12]. Which option represents the partially sorted list after three complete passes of bubble sort?
[1, 3, 7, 9, 10, 8, 12, 13, 15, 19]
[1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
[1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
[1, 7, 3, 9, 10, 13, 8, 12, 15, 19]
10. The algorithm for bubble sort requires a pair of nested loops. The outer loop must iterate once for each element in the data set (of size n) while the inner loop ….
def shortBubbleSort(alist):
exchanges = True
passnum = len(alist)-1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i]>alist[i+1]:
exchanges = True
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum = passnum-1
alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)
iterates n times the first time it is entered, n-1 times the second, and so on
iterates 5 times the first time it is entered and 5-1 times the second
None of the above
iterates an infinite number of times until n = 1
11.
A Bubble sort's O(n2) complexity means that its efficiency ______on lists of more than a small number of elements
12. What are the correct intermediate steps of the following data set when it is being sorted with the bubble sort? 15,20,10,18
All of the above are valid options
15,10,20,18 -- 15,10,18,20 -- 10,15,18,20
10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20
15,18,10,20 -- 10,18,15,20 -- 10,15,18,20 -- 10,15,18,20
13. It is possible to code a bubble sort with two 'for loops' nested in each other
14. What is the maximum number of comparisons if there are 5 elements in array x?
15. What is the max. number of comparisons that can take place when a bubble sort is implemented? Assume there are n elements in the array?
16. In the following code, what is the line for i in range(n) doing?
17. What is the advantage of bubble sort over other sorting techniques?
18. The given array is arr = {1,2,4,3}. How many iterations would be required to use a bubble sort to sort this?
19. The maximum number of comparisons would be required if the numbers are all in reverse e.g. 6,5,4,3,2,1 and…
20. The best case scenario in a bubble sort would be ____________. The list is sorted, so it's done!
21. A programmer has a list of numbers in an array called scores, as shown below. When setting up a bubble sort algorithm, a variable called swaps which can either be True or False is used. Fill in the blanks.
22. Bubble sort is a comparison based algorithm that compares each ___________
in an array and swaps them if they are out of order until the entire array is sorted.
23. The Bubble sort is widely considered the most practical sorting algorithm for very large unsorted lists.
24. Consider the example below for the numbers 5,1,4,2,8 - what comes next?
First Pass
( 5 1 4 2 8 ) {\displaystyle \to } \to ( 1 5 4 2 8 ), 5 > 1.
( 1 5 4 2 8 ) {\displaystyle \to } \to ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) {\displaystyle \to } \to ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) {\displaystyle \to } \to ( 1 4 2 5 8 ), (5 > 8), algorithm does not swap them.
Second Pass
( 1 4 2 5 8 ) {\displaystyle \to } \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) {\displaystyle \to } \to ( 1 2 4 5 8 ),
What comes next?
Swap since 4 > 2 resulting in: (2,1,4,8,5)
set of elements (of five elements or greater)
individual element against the last element
Do not swap since 4 > 2 resulting in: (1,4,5,8,2)
25. In computer graphics bubble sort is popular for its capability to detect a very small error (like swap of just two elements) but is otherwise ….