2S2122 Activity 1.2

Instructions

• For our programming exercises, we will use Google Colab.
  • If you are familiar with Jupyter Notbook then you probably would know how to use Google Colab.
  • It's an open source mark down language with Python support. Almost exactly like Jupyter.
  • Discovering how to use Google Colab is part of your homework. Go ahead and tinker with it.
• Submission guidelines are as follows:
  • For every programming exercise, you are to submit your .ipynb file into your respective submission bin.
  • To download your .ipynb file, first in your Google Colab page go to File > Download > Download .ipynb file.
  • Don't forget to rename your .ipynb file with the following format "class_lastname_firstname_studentnumber.ipynb".

Programming Problem

Your main task is to create a bubble sort function that takes in some list as input and prints each row iteration until we reach the final sorted list. You need to sort the input list in ascending order. The .ipynb that you will use is in our UVLE page. Please find it there. A few things that we want for our program:

• The sorting must be in ascending order.
• It only takes in an input list (we prepared this for you already).
• Use function recursions. Go research what this means. If you can't do recursions (because you opt to use for loops only) that's fine but your final max score would be 8 pts. out of 10 pts.
• Don't forget to put in your student number in the function that generates a random list. We'll use your student number as a seed for the random number generator.
• Print each pass in your program. Each pass is one row sweep. Here's a short example:

Suppose the input list is:

[2, 93, 54, 79, 87, 10, 95, 19, 18, 12]

The expected output would be:

[2, 54, 79, 87, 10, 93, 19, 18, 12, 95]
[2, 54, 79, 10, 87, 19, 18, 12, 93, 95]
[2, 54, 10, 79, 19, 18, 12, 87, 93, 95]
[2, 10, 54, 19, 18, 12, 79, 87, 93, 95]
[2, 10, 19, 18, 12, 54, 79, 87, 93, 95]
[2, 10, 18, 12, 19, 54, 79, 87, 93, 95]
[2, 10, 12, 18, 19, 54, 79, 87, 93, 95]

Each row indicates a sweep of swaps. For example, from the original input list, we need to swap 93 and 95 several times for the first sweep. For the 2nd row, carrying over from the previous sweep, we need to swap 87 and 93 several times for the second sweep. This continues until we reach the final answer. Below is another example. Suppose a different input is:

[14, 98, 25, 68, 50, 13, 36, 62, 73, 64]

The expected output is:

[14, 25, 68, 50, 13, 36, 62, 73, 64, 98]
[14, 25, 50, 13, 36, 62, 68, 64, 73, 98]
[14, 25, 13, 36, 50, 62, 64, 68, 73, 98]
[14, 13, 25, 36, 50, 62, 64, 68, 73, 98]
[13, 14, 25, 36, 50, 62, 64, 68, 73, 98]

In the first pass, we needed to swap 98 up to the end of the list. In the second pass, we needed to swap 68 and 73. The bubble sort algorithm continues until we get our final sorted answer.

Some Details About the Activity

You only need to fill in the contents of the bubble sort function. Particularly on:

def bubble_sort(list_to_sort):
  #Insert nice code in here

There is a pre-made function that generates a random list of 20 numbers from 0 to a 100 without repetition. Strictly don't change anything in this function. However, in the set-up portion, please change the input to your student number. The pre-made function is shown below.

def gen_random_list(sn):
  random.seed(sn)
  rand_list = []

  for i in range(20):
    temp_rand = random.randint(0,100)

    while(temp_rand in rand_list):
      temp_rand = random.randint(0,100)

    rand_list.append(temp_rand)

  return rand_list

Grading Rubrics

• If your program works AND you used function recursions, you get 10 full points.
  • You can use at most 1 for loop for this case.
• If your program works BUT you did not use function recursions, you only get 8 points.
  • This is when you use 2 or more for loops.
  • For loops have high complexity, that's why we try to use recursions instead.
• No submission or the code doesn't work is automatically 0 points.