Sorting to be efficient

There are many search algorithms we have seen during our years in school.  Maybe some of you know more types of searching.  We can see that

Bubble sort is the worst search algorithm most of us has seen.  As a review, bubble sort is when we compare the first number with the second and switch them if the first is larger than the second.  Then we repeat this for the second and third number and so on until we compare the last two numbers in a list.  Then we repeat this process n times where n is the length of the list.  Each time the process is executed, the highest number is dragged to the top, then the second highest is moved before the highest and so on.  Many can see why this algorithm is terrible.  To those that don't, consider this, the list is most likely sorted halfway through the algorithm, and yet the loop will continue to execute, wasting your precious time when you could be enjoying playing other games while you have bubble sort order your list which contains 100000 numbers.  If we examine the runtime of this algorithm, we find that the time as n increases, grows quadratically.

Merge sort is one of the best search algorithms we seen.  As a review, merge sort is when we break up a list into two about equal length (what about when the length of the list is odd?) list and we recursively do this until we have a list of 1 item.  Then the list are sorted individually and combine with its complementary list.  To form the new list from the two smaller list, compare which is the smallest value from the two list and append it to the new list, compare the second smallest value with the value that was not chosen and append the smallest of that and so on until either list have exhausted all values.  This is very efficient and we find that as n increases, the runtime increases logarithmically.

From these two examples of sorting, we can imply that sorting algorithms have different runtime but may grow similarly with another algorithm.  For instance, selection sort and insertion sort has different runtime but as the list increases, the runtime increases at the same rate.  Runtime is important for analysing sorting but this idea can be expanded.  For instances, programmers use it to analyse the program they make.  It is important for a programmer to know the runtime so that he/she can make it more efficient unless you like to wait for a large amount of time for one process to be finished.

Binary trees

A tree is composed of three parts: a root, children and leaves.
From the ground to the sky, the first part of a tree is the roots, then comes the trunk (no name for it in a binary tree), then it spreads out into branches (or children), and finally the leaves

This is an example of a tree where the leaves are digits and the children and root are mathematical symbols

(3 + (5 - 2))* 9

Recursion

Recursion is a technique where the method will call itself and execute its code.  A recursive method will continue to call itself until it reaches a "terminating condition" and it would start to work backwards

Although this sounds ridiculous, you could think of recursion like this.  You have a large, plastic bag.  You want to give your friend his gift.  You get his gift from your bag, instead, you pull out another smaller, plastic bag and from this bag, you pull out another plastic bag (and no, those plastic bags are not for his friend) until you reach your incredibly fragile gift.

Or if you hate reading this and want to see what I am saying, here's a video you may remember from your childhood: http://youtu.be/PJg-HMlCR0M?t=3m15s 

Although this example makes it sound like you do lots of meaningless work, it isn't.  Recursion could become a more useful technique than implementing "for" or "while" loop.  Would you want to use a loops, and accumulators and be less efficient?

The hardest part recursion for me would be to make sure that the function has a terminating condition.  As demonstrated in class, if we didn't have this condition, our functions would exceed the memory our poor computers have given Python to use.  You not only have to make a terminating condition, you have to have the right conditions or else the function ends prematurely or never ends at all due to some unforeseen case when you run a code.

Object oriented programming

As a student, learning about programming, I thought to myself, how is object-oriented programming suppose to be different from what we programmed in CSC108?  The answer was not about the argument representing an object, it was about what we do with the argument and you know what, it did not make me smile that much.

To me, when we programmed in CSC108, we specified whether an argument is an integer, a float, a string, etc.  Now we just replace those arguments with a more general type, which is "object".  I like to think of how we use to program as if it was a library.  The shelves were methods and the books are the arguments where the shelf will want you to place a specific genre of books and not other genres.  Now it feels like we have boxes representing methods and we put objects (hmm, what a coincidence?) into that box.  The box does not prefer a specific object unlike the shelves which would prefer a certain genre of books.

Realistically, object-oriented programming is not different from how we use to program, all we have to do is add more code.