05 - Bubble Sort

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

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

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

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

Note: Play with the Bubble sort to see how it works

  swap

  deletion

  insertion

  pass

  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

Bubble sort can be practical if the input is in 
_________________ with some out-of-order 
elements nearly in position.

  mostly sorted order

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

  the middle of another list

  completely unsorted order

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, 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

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

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

  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)

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

  TRUE

  FALSE

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

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

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

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

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

  increases

  multiplies

  subtracts

  decreases

  All of the above are valid options

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

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

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

  FALSE

  TRUE

  6

  5

  2

  10

  (1/2)n(n-1)

  (1/2)(n-1)

  (1/4)n(n-1)

  None of the above

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

  It is performing the swap FOR every element that is greater

  It always takes less memory

  It is capable of detecting whether the input is already sorted

  All of the above

  It is always faster

  4

  2

  1

  3

  The max no. is 10 >> n - 1

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

  None of the above

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

  one pass

  two passes

  n passes for a list of size (n)

  no pass (zero pass)

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.

  True

  False

  > length of scores

  < length of scores

  quadruple of elements

  individual element against the last element

  pair of elements

  set of elements (of five elements or greater)

  TRUE

  FALSE

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

  False

  True

  set of elements (of five elements or greater)

  very practical especially for large lists

  not very practical, especially for large unsorted lists

  individual element against the last element