01 - Bubble Sort

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

  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

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

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

  swap

  pass

  deletion

  insertion

  because it was created by Mr Bubble Smith Taylor

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

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

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

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)

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 two numbers around. If not, do not swap

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

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

  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)

  3, 2, 4, 1, 5 (2<3 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?
__________________________________________

  5,4,1,3,2 (Second Pass completed)

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

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

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

  FALSE

  TRUE

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

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

  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

  None of the above

  iterates an infinite number of times until n = 1

  multiplies

  increases

  subtracts

  decreases

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

  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

  FALSE

  TRUE

  2

  6

  5

  10

  (1/4)n(n-1)

  (1/2)n(n-1)

  None of the above

  (1/2)(n-1)

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]

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

  None of the above

  It is performing the swap FOR every element that is greater

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

  It is always faster

  It always takes less memory

  All of the above

  It is capable of detecting whether the input is already sorted

  3

  2

  1

  4

  The max no. is 10 >> n - 1

  None of the above

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

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

  no pass (zero pass)

  two passes

  n passes for a list of size (n)

  one pass

  2,13,6,10,12,4

  2,6,13,8,9,10,12,4

  2,4,6,8,9,10,12,13

  None of the above

  individual element against the last element

  set of elements (of five elements or greater)

  pair of elements

  quadruple of elements

  TRUE

  FALSE

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)

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

  individual element against the last element

  very practical especially for large lists

  set of elements (of five elements or greater)

  individual element against the last element

  not very practical, especially for large unsorted lists