Preview

05 - Bubble Sort

 1. Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted and….

  compares each pair of adjacent items and swaps them if they are in the wrong order

  All of the above are possible depending on the length of the list

  compares the second element with the last element and performs a swap

  compares the first element with the last element and swaps them if in wrong order

 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.
Note: Play with the Bubble sort to see how it works

  insertion

  swap

  pass

  deletion

 3. Why is it called 'Bubble' sort?

  because the elements that are compared are deleted, like bubbles being popped

  because it was created by Mr Bubble Smith Taylor

  because of the way smaller or larger elements "bubble" to the top of the list.

  It was a random name given to it by the creators of the sort

 4. The Bubble sort is quite simple to code, but too slow and impractical for most problems. Fill in the blanks..
Bubble sort can be practical if the input is in 
_________________ with some out-of-order 
elements nearly in position.

  the middle of another list

  completely unsorted order

  mostly sorted order

  high numerical sequence (e.g. very large numbers)

 5. Consider the steps below for a bubble sort algorithm. Can you fill in the blanks?
The algorithm for Bubble Sort
=========================
1 - Look at the first number in the list.
2 - Compare the current number with the next number.
3 - Is the next number smaller than the current number? 
4 - ____________________________________________________.
5 - Move to the next number along in the list and make this the current number.
6 - Repeat from step 2 until the last number in the list has been reached.
7 - If any numbers were swapped, repeat again from step 1.
8 - If the end of the list is reached without any swaps being made, 
then the list is ordered and the algorithm can stop.

  If so, swap the two numbers around. If not, do not swap

  If so, insert the smaller number to the end of the list

  If so, do not swap and insert the last element into the first

  If so, swap the first element for the last element and continue to do so

 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)

  5, 2, 4, 1, 5 (3<5 so the two values are 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)

 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)

  2, 3, 1, 4, 5 (First pass completed)

  1,3,2,4,5 (Second 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.

  FALSE

  TRUE

 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, 9, 19, 7, 3, 10, 13, 15, 8, 12]

   [1, 3, 7, 9, 10, 8, 12, 13, 15, 19]

  [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)

  None of the above

  iterates an infinite number of times until n = 1

  iterates 5 times the first time it is entered and 5-1 times the second

  iterates n times the first time it is entered, n-1 times the second, and so on

 11. A Bubble sort's O(n2) complexity means that its efficiency ______on lists of more than a small number of elements

  decreases

  increases

  subtracts

  multiplies

 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

  15,18,10,20 -- 10,18,15,20 -- 10,15,18,20 -- 10,15,18,20

  All of the above are valid options

  10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20

  15,10,20,18 -- 15,10,18,20 -- 10,15,18,20

 13. It is possible to code a bubble sort with two 'for loops' nested in each other

  FALSE

  TRUE

 14. What is the maximum number of comparisons if there are 5 elements in array x?

  10

  6

  5

  2

 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?

  (1/2)n(n-1)

  (1/2)(n-1)

  None of the above

  (1/4)n(n-1)

 16. In the following code, what is the line for i in range(n) doing?
def bubbleSort(arr):
    n = len(arr)
 
   
    for i in range(n):
 
        # Last i elements are already in place
        for j in range(0, n-i-1):
 
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

  None of the above

  It is performing the swap FOR every element that is greater

  It is looping/traversing through all the elements in the array (or list)

  It is performing the swap FOR every element that is smaller than the first element

 17. What is the advantage of bubble sort over other sorting techniques?

  It is always faster

  All of the above

  It is capable of detecting whether the input is already sorted

  It always takes less memory

 18. The given array is arr = {1,2,4,3}. How many iterations would be required to use a bubble sort to sort this?

  2

  1

  3

  4

 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…

  The max no. is 15 >> n(n-1)/2

  None of the above

  The max no. is 10 >> n - 1

  The max no. is 5 >> n + n * 2

 20. The best case scenario in a bubble sort would be ____________. The list is sorted, so it's done!

  two passes

  one pass

  no pass (zero pass)

  n passes for a list of size (n)

 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.
Array: scores
========================
17	9	4	-12	3	39


The boolean variable swaps is initialised to False at the start of
the algorithm.

If pairs of numbers are swapped, set to _______
When all numbers have been compared, check again…
… if swaps is ________, repeat algorithm / process again
…setting swaps back to False.
bsort.gif

  False

  > length of scores

  < length of scores

  True

 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.

  quadruple of elements

  individual element against the last element

  set of elements (of five elements or greater)

  pair of elements

 23. The Bubble sort is widely considered the most practical sorting algorithm for very large unsorted lists.

  FALSE

  TRUE

 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?

  Do not swap since 4 > 2 resulting in: (1,4,5,8,2)

  Swap since 4 > 2 resulting in: (2,1,4,8,5)

  individual element against the last element

  set of elements (of five elements or greater)

 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 ….

  set of elements (of five elements or greater)

  very practical especially for large lists

  individual element against the last element

  not very practical, especially for large unsorted lists