Computing $7$ Assignment

Background

In this assignment, you will be extracting daily temperature data, sorting the data, and then calculating the median temperature for a given set of data.

A set of daily temperature data will be provided to you as a list of strings. For example:

temps $=["5","-1\mathrm{.}0","1\mathrm{.}1",$"None","$9","$NA$","1\mathrm{.}0"]$

Note that the temperature may not be recorded on some days. A sequence of characters that cannot be represented as a number indicate that the temperature was not recorded on a given day. In the previous example, we can see that the strings "None" and $"$NA$"$ were used to represent days where the temperature was not recorded. It is important to note that these strings can consist of any characters and can vary in length. Some more examples would be $""($the empty string$),$ "Nothing", "Not recorded", "Forgot", etc.

To calculate the median temperature for a given set of data, we first need to convert the data to a list of numbers. The data converted from the temps list is given below. Notice how the days that did not have a recorded temperature were ignored:

temps$\_$extracted$=[5\mathrm{.}0,-1\mathrm{.}0,1\mathrm{.}1,9\mathrm{.}0,1\mathrm{.}0]$

How would we calculate the median of our list? Recall that the median is a value separating the higher half from the lower half of a list of sorted values. In the case where the length of our list of numbers is odd, the median is the middle element in our list. In the case where the length of our list of numbers is even, the median can be found by taking the average of the two center most elements.

We cannot calculate the median until we sort our values. Our sorted temperatures will look as follows:

temps$\_$sorted$=[-1\mathrm{.}0,1\mathrm{.}0,1\mathrm{.}1,5\mathrm{.}0,9\mathrm{.}0]$

Now that our list is sorted, we can see that the median in this case is $1\mathrm{.}1.$

So how do we sort a list of values? Formally, a sorting algorithm is a sequence of steps that are used to sort a sequence of values. It turns out that there exist many different sorting algorithms, some more complicated than others. In todays assignment we are going to focus on an intuitive sorting algorithm known as selection sort. We are going to use this algorithm to sort a list of numbers in ascending order.

Say we have a list named nums. The main idea of selection sort is that we want to start iterating over our list nums from i $=0$ to the length of our list minus $1($n$-1),$ choosing the smallest element in the sub list from nums$[$i$]$ to nums$[$n$-1]$ and placing it in nums$[$i$]$ on each iteration. If you are confused, don't worry! We have provided you the pseudocode for the algorithm. Before looking at the pseudocode, use the following example to gain some intuition about how selection sort works.

Imagine that we have the following list of numbers that need to be sorted:

alg$\%20\%2826\%29.$png

We start sorting at the left most item. We call our current position index i$.$ The left most element in our list is the number $2,$ which occurs at i $=0.$

alg$\%20\%2825\%29.$png

When considering the final sorted list, should the number $2$ be in this position? What is the smallest element in our list from index i to the end of our list $($index $4)?$ By inspection, we can see that the smallest number is $1.$ We can identify the position of this number using the variable min$\_$index, which in this case is min$\_$index $=2.$ Therefore the number $1$ should be at index i because it is the smallest element in our list from index $0$ to index $4!$

alg$\%20\%2824\%29.$png

We can guarantee that the number $1$ will be in the correct position in our final sorted list if we swap the elements at i and min$\_$index!

alg$\%20\%2823\%29.$png

You might think that $2$ is still not in its correct position, but don't worry! We can guarantee that the number $1$ is in the correct position, and we will worry about $2$ later.

Let's now increment i to $1.$alg$\%20\%2821\%29.$png

Let's perform the same actions we did when i was $0.$ What is the smallest element in our list from the element at this position $($i $=1)$ to the end of our list $($index $4)?$ By inspection, we can see that the smallest number is $2$ which occurs at index $2,$ thus min$\_$index $=2$ in this case.

alg$\%20\%289\%29.$png

We then swap the elements at i and min$\_$index!

alg$\%20\%2811\%29.$png

Let's now increment i once again to $2.$

alg$\%20\%2812\%29.$png

Can you see what's going on here? All of the elements $($green$)$ to the left of our current index i are sorted! Therefore our entire list will be sorted if we continue with this algorithm until we reach the end of our list. The following illustrations demonstrate how the algorithm will perform for the rest of the list.

alg$\%20\%2820\%29.$pngalg$\%20\%2814\%29.$png

Increment i once again.

alg$\%20\%2815\%29.$pngalg$\%20\%2819\%29.$pngalg$\%20\%2817\%29.$png

When we increment i one last time, we reach the end of our list and all elements are sorted!

alg$\%20\%2818\%29.$png

The pseudocode for the algorithm is given below. We assume that the list we are sorting is given by the name nums.

Create a variable n and set it equal to the length of nums

For i $=0$ to n$-1$

Create a variable min$\_$index, a