Week 11 - Sorting and Efficiency

So during this week, sorting and efficiency was discussed and the ways to categorize them. There are many kinds of sorts such as the shellsort, insertion sort, selection sort, bubble sort, quick sort and many others; each producing a sorted list whilst using different and or hybrid methods to sort. And it is this difference in methods that allow for different sorts to have different run time or efficiency.

                Take bubble sort for example, I can say that the big-Oh for this type of sort is n² and this makes sense. Consider a list with 1 million items, the worst case scenario in this case would involve running 999,999 iterations which is approximately x². Bubble sort runs by taking the item in question and comparing it to the value next to it. If it is bigger it shifts the item to the right otherwise, it stays the same and the next value is the new item in question. It runs constantly through all the items in the list in which the list gets shorter by n-1 times. So what is big-Oh? Big-Oh simply indicates the scaling of the algorithm as the size of the list if items increases indefinitely in the worst case scenario. Therefore, big-Oh value of n² means it will take n² times long as the list grows big. In blunt efficiency terms, it’s a terrible sorting algorithm to use for long lists.

                Another more efficient example is the merge sort. In this case, the value of big-Oh is n log(n) and this can be explained by the nature of the sort. Merge sort uses a divide and conquer approach where it breaks the list into 2 constantly, relative to the first item in the list. I.e. the items that are bigger or equal to the first item and the items that are less that the first item. This is run many times until all the smaller broken up list are properly sorted and then the merge begins. The breaking into two separate parts constantly is the reason behind the log(n) and the n comes from figuring out the items that are bigger or smaller than the first item in the list.

                These analysis of worst case run times can be used to identify good sorts but more importantly choose the right sort for the problem in question. For example, although bubble sort has a big-Oh value of n² if the list is very close to being sorted, the best case scenario for bubble sort becomes n. n being much more efficient then n² even though it is the same sorting algorithm.

Week 10 – The Test…

                Well it was test week and I can just say it was terrible. I completely blanked out when it came to the question that involved linked lists. The structure of linked lists in combination with the fact I had to recursively find an answer only made the question even more puzzling during test time. As mentioned before, I detest linked lists and when its use was required during the test, it made me panic half way through the test.

                It wasn't until after the test I look through the notes to see how one makes and uses linked list and after comparing what I remember written on the test, it made me depressed and very frustrated. I don’t quite remember the question specifically, however the major problem I had with the problem was recursively building the list of nodes and returning and maintain the built up list as it moves up the recursive iterations. It turns out I was over thinking the question and that all it was required was a return statement that automatically goes up if it is correct. That is what I call… a major failure. Hopefully, I can learn from this stupid mistake and move on with my life with the final exam.        

Week 9 - Binary Search Trees

So this week was about binary search trees and how to use them to sort data in a useful format. Essentially, binary search trees are a series of nodes each containing a left node and a right node along with a value, root. It is organized by relative size to one another in that all items that is greater than the root goes on the right side of the node in question, and everything that is smaller than the root goes on the left side. It was also learned that the binary search tree is recursive in nature and it makes sense due to the property of the nodes in that it potentially has a left and or right node. Therefore at any given node, it may branch into two “separate” binary tree with all the properties of a binary search tree intact.

I remember doing this back in high school however I realize that we have never touched recursion. Yet alone finding items in a pre-built binary search tree. However, considering that I am aware of how binary search trees work and know it behaves, I’m confident that the only thing I need to work on is the technical aspect of having to manipulate the nodes in Python rather than Java.