Sorting

     In everyday life, sorting means to arrange a collection of elements in a certain way, for example arranging a deck of cards in increasing order. There are many different ways to sort a deck of cards but what would one have to do to sort a whole deck in the least amount of time?

     Through our lectures we learned many algorithms to sort a Python list and which of these algorithms were more efficient when compared to each other. We compared the algorithms using Big-O Notation which counts the number of steps that get executed when trying to sort a list of n items. One of the sorting algorithms we looked at was Selection Sort:

1	def selectionSort(alist):
2	for fillslot in range(len(alist)-1,0,-1):
3	positionOfMax=0
4	for location in range(1,fillslot+1):
5	if alist[location]>alist[positionOfMax]:
6	positionOfMax = location
7
8	temp = alist[fillslot]
9	alist[fillslot] = alist[positionOfMax]
10	alist[positionOfMax] = temp
11
12	alist = [54,26,93,17,77,31,44,55,20]
13	selectionSort(alist)
14	print(alist)

     (code from Interactive Python - Sorting)

     From the code above, we say that the selection sort algorithm is O(n^2) because when sorting a list of n elements, the outer for loop runs n times as with the inner for loop. This runtime complexity is quite inefficient when compared to the Quick Sort or Merge Sort algorithms which have O(nlogn) complexity on average.

     My goal when it comes to sorting is to learn the complexities of the worst and best cases of the algorithms we've learned, and most importantly, to understand why it has that specific complexity. To achieve this I will practice tracing the code for the algorithms, trying to notice the lines of code that get executed the most (such as the nested for loop in the example above). 

A Revisit to Recursion

     In the beginning of the course we were introduced to an important concept of programming called recursion. Just to remind ourselves, a recursive function is one that calls itself and is used in order to solve a problem which can be broken down into smaller instances. A recursive solution is found by first solving the simplest instance (or base case) of a complex problem then using that solution to find a solution to a more complex instance, then using that solution... and you get the point by now.

     Since our introduction to recursion, we have practiced writing recursive code whether it was through finding the sum of a nested list, drawing with Python's turtles, stacking cheeses or through creating trees. These examples and practice problems during labs really helped me when it came to writing recursive code for our first test. Using the Tree class, one of the problems was to write a function two_whether which returned whether at least one value in a Tree is 2. It looked something like this:

class Tree:

    """Bare-bones Tree ADT"""

    def __init__(self: 'Tree', value: object=None, children: list=None):

        "Create a node with value and any number of children"""

        

        self.value = value

        if not children:

            self.children = []

        else:

            self.children = children[:]

def two_whether(t: Tree) -> bool

    "Return whether at least one value in tree is 2

    precondition - t is a non-empty tree with number values

    >>> tn1 = Tree(2, [Tree(4), Tree(4.5), Tree(2), Tree(5.75)]

    >>> two_whether(tn1)

    True

    """

    return t.value == 2 or any([two_whether(x) for x in t.children])

    The base case in this example was if t.value == 2, and the recursive part was searching through the children of the Tree if any of their values were == 2. 

    One of my goals in this class is still to master recursion, and after being able to answer that question on the test I feel like I am reaching closer to my goal.