Sorting and Efficiency

Sorting is essentially a way of taking a list of unordered elements and ordering them in a specific way, e.g. smallest-to-greatest or greatest-to-smallest. However, there is one key difference between sorting items via programming and sorting items requires an algorithm. An algorithm is a set of instructions that will test elements and put them in a certain place according to a rule.There are multiple ways of doing this, each with pros and cons. In this post, I will primarily discuss three types of sorting: bubble sort, selection sort, and insertion sort.

Bubble sort employs an algorithm that goes through every index in a list, and checks if the item at that index is greater than the item succeeding it. If it is, it swaps the item, this process continues until the function reaches the second last index, at which point the list is sorted. The diagram below illustrates the method of sorting.

Taken from http://mytutorialspace.com/bubble-sort/

Selection sort. The first pass of this sorting algorithm takes the smallest item in the list and places it at index 0, i.e. at the start of the list, thus creating a sorted and sorted side of the list.After the first pass, the sorted section is comprised only of the item at index 0; this is the only item that we know for certain is sorted. The next pass will take the smallest item in the unsorted section and move it to index 0 of the unsorted section, i.e. one index after the end of the sorted section. In this way, the sorted section will be comprised of two sorted numbers in the next pass. The size of the sorted section will increase by one, and the unsorted section will decrease by one. This process continues until the length of the unsorted section equals one. This means that the item in the unsorted section is the largest number. Hence, the list is sorted. The diagram below clearly illustrates this concept.

Red: sorted, Blue: unsorted
Taken from http://mytutorialspace.com/write-program-demonstrate-selection-sort-array/

Insertion sort. This algorithm starts by taking the first two indexes, 0 and 1, and comparing their sizes. It will swap them if index 0 is larger than index 1. Otherwise, it will do nothing. After this occurs, index 0 and 1 can be considered a sorted region. The rest, for all we know, are unsorted. The algorithm then moves forward one index at a time and checks if the item at that index is less than any of the items in the sorted region. If it is less, the sorting algorithm will move that item behind the item that it is closest to it in size, but still greater than it. Otherwise, the algorithm will proceed to the next index. This continues until the end of the list. The diagram below show this concept.

Red: sorted, Blue: unsorted
Taken from http://www.stoimen.com/blog/2012/02/13/computer-algorithms-insertion-sort/

Efficiency. Each of these algorithms have different time complexities, they require different amounts of time to output the desired result.

To measure these time complexities, the standard is to use Big-Oh. O(n) means the sorting algorithm indexes every item in the list, where n represents the amount of items. O(1) means that the sorting algorithm's time complexity. It is invariable, so we represent it using a constant value, i.e. 1.

Week8: Linked Lists

This what they look like:

One lists links to another list.

Week 7: Recursion for realz this time

You just keep doing it over and over again.
Essentially recursion is a function that calls itself in order to complete whatever task you desire.

In order to use recursion there has to be:

• a pattern or specific sequence that repeats it self.
• a base case so the computer knows where to start.
• a function that does something

The concept of recursion is not too difficult to understand, but its not as simple as it looks.

This stuff gets pretty confusing when you have some whacky sequence. 

Creating a recursive function ezpz once you get the base case, luckily if you're good with recognizing patterns you can get that base case. Unfortunately I am not that person.

 Here for some examples.
    

    Next example:

    

A2 Part 2

It wasn't that bad...

Week 6: Trees

Trees have branches and leaves. 
Built-in function. They makes code shorter and the program more efficient. See Built-in Functions .
          1. all(iterable)

    Return True if all elements of the iterable are true (or if the iterable is empty).

2. any(iterable)

    Return True if any element of the iterable is true. If the iterable is empty, returnFalse.

3. filter(function, iterable)

    Construct an iterator from those elements of iterable for which function returns true. iterable may be either a sequence, a container which supports iteration, or an iterator. If function is None, the identity function is assumed, that is, all elements ofiterable that are false are removed.

4. map(function, iterable, ...)

    Return an iterator that applies function to every item of iterable, yielding the results. If additional iterable arguments are passed, function must take that many arguments and is applied to the items from all iterables in parallel. With multiple iterables, the iterator stops when the shortest iterable is exhausted. For cases where the function inputs are already arranged into argument tuples, seeitertools.starmap().

5. repr(object)

    Return a string containing a printable representation of an object.

6. zip(*iterables)

    Returns an iterator of tuples, where the i-th tuple contains the i-th element from each of the argument sequences or iterables. The iterator stops when the shortest input iterable is exhausted. With a single iterable argument, it returns an iterator of 1-tuples. With no arguments, it returns an empty iterator.

                         >>> x = [1, 2, 3]
                         >>> y = [4, 5, 6]
                         >>> zipped = zip(x, y)
                         >>> list(zipped)
                         [(1, 4), (2, 5), (3, 6)]
                         >>> x2, y2 = zip(*zip(x, y))
                         >>> x == list(x2) and y == list(y2)
                         True

 

    We wrote some equivalent code during the lab using non-built-in functions. But use of built-in functions as well as built-in modules is of great importance to program in python.

 

Week 5: Name Names

Variables are stored differently. Now you know.
def scope_test():
    def do_local():
        spam = "local spam"
    def do_nonlocal():
        nonlocal spam
        spam = "nonlocal spam"
    def do_global():
        global spam
        spam = "global spam"
    spam = "test spam"
    do_local()
    print("After local assignment:", spam)
    do_nonlocal()
    print("After nonlocal assignment:", spam)
    do_global()
    print("After global assignment:", spam)

scope_test()
print("In global scope:", spam)

Week 4: More Recursion

Okay, so we're back to recursion this week.
In case you forgot recursion is a process computer scientists use to make their lives easier.
Essentially recursion calls upon the same function over and over again until their problem is solved. Recursion is used when theres some sort of pattern or sequence.
Recursion requires a base case and the sequence you're trying to solve.
Trying to do recursion without a base case is a big no-no...
If you do this you are a wicked person.
You will send the program to recursive hell if there is no base case.
Essentially the function will keep calling itself over and over again until the program cries..."maximum recursion depth reached". What kind of monster could do such a thing to a computer???!?

Anyway, if you find yourself repeating yourself, use recursion and call it a day.