week_11: Sorting algorithms and efficiency

Firstly here're some important sorting algorithms we've seen in CSC108 and CSC148:Bubble Sort, Selection Sort,  Insertion Sort, Quick Sort, Merge Sort.

The chart, which I made myself, shows how they work in best and worst cases with respect to Big-Oh and here're the reasons why they act this way.

Bubble Sort
It starts on the left and compares the adjacent items and keeps bubbling the larger one to the right. In the best case, we just need to compare 1 pass coz everything's in order and no swaps are made, but it still takes n times. In the worst case, we need to compare n - 1 passes and each pass there's a swap, then it takes (n -1) + (n - 2) + ... + 3 + 2 + 1 steps, thus we get O(n ^2).

Selection Sort
It finds the largest item throughout the list and swap it with the last item, then it finds the largest item in the list regardless of the last one since it's already in the correct position, and so on. Thus it sees the two lists 1, 2, 3, 4, 5 and 5, 4, 3, 2,1 the same since it just finds the largest item each iteration thus causes (n - 1) + (n- 2) + ... + 2 + 1 comparisons. So its efficiency is independent of the data.

Insertion Sort
It maintains a sorted sublist from the left and each new item is inserted to the previous sublist s.t the sorted sublist is one item larger. Thus the worst case takes (n - 1) + (n- 2) + ... + 2 + 1 steps to insert each new item in the right place. The best Case, just append every new item to the sublist, which takes n times. 

Merge Sort

As I described in the previous Blog, the dividing step takes logn times and then the merge step takes always a + b times to compare each two pairs of length a and b, respectively, then merges them into one larger list. Thus the whole comparison steps takes n times. Thus the whole Sorting process takes n times logn steps. Then it's clear the best and worst case take the same runtime.

Quick Sort

Here we need to emphasize on the best case and worst case. The best case, e.g. 2, 1, 3, thus each partition in exactly in the middle, as in Merge, this partition takes logn times. Plus there's n times, so the best case takes nlogn. The worst case is surprisingly a sorted array, since this causes the partition step takes (n - 1) + (n- 2) + ... + 2 + 1 steps. For example, Instead of breaking an 8 element array into arrays of size 4, 2, and 1 in three recursive calls, the array size only reduces by one: 7, 6, and 5. Thus the worst case is O(n^2).

week_10 sorting methods, e.g. quick and merge

I still remember when I was in CSC108, 3 typical sorting algorithms has been introduced vividly in class by working with toys and candy jars of different heights, which are selection sort, insertion sort and bubble sort. And this week some more complicated sorting methods are introduced. Here I'll take quick sort and merge sort for example.

QuickSort. We start by choosing a pivot point as a reference and we pull the items less than the pivot out and also the items greater than the pivot and create a two lists containing them separately. Then we then we quick-sort these two lists and finally by recursive, thus our list is sorted. Notice every time we get these two featured lists, the final position of our pivot is found. Thus every time we cut our list roughly into two halves according to the value of our pivot. We shouldn't assume that our pivot is the first item of our list, it can be random, which also helps save time.

MergeSort. We start by continuing cutting our list in to two halves until we reach the base case, i.e. length of list is 1. Then here's a significant function called merge, which takes two smaller lists and combines them together into a single, sorted list. In this way we get our list sorted properly. But it requires much more spaces since our list is cut into n slides. 

week_9: BST & BSTNode

I must say that BST is really a great invention derived from a regular binary tree. It's been very beautifully constructed since every value goes into a proper position, which saves a great amount of time when we want to find an item or insert one. So a BST, i.e a Binary Search Tree, is a ordered tree such that the left subtree of any node contains only keys that are less than the node's key and at the same time the right subtree of any node contains only keys that are greater than the node's key. Thus, there should't be duplicated nodes. What's more, the left and right subtree of a node must be BST as well. So you can see that everything in a BSTree is already sorted, which is always good since it's neat and clear and we can do lots of stuff with this great property.  Also we derived three kinds of traversal out of a BST: in-order, pre-order and post-order. Each of them gives us a "sorted" list representing a BST. Using recursive, codes become neat and clear since when you run it by hand, a sort of pattern revealed itself, that's way I love these traversals.
The BSTNode, just like LLNode, represents the nodes in a BST. We can implements classes in different ways, which was exactly what we were working with in the lab and it was kinda frustrating, I figured I had too little practice on recursive functions. Things don't seem hard at first sight but I just can't working around comfortable with them. I guess I have to work harder and not try to remember patterns, as I always did.

week_8 LinkedList & LLNode

This week we've been introduced to a new class LinkedList. It seemed nothing special when I first saw it. A LinkedList class can be seen as a more systematic way to operate on lists. And LLNode is merely more focused on every node in a LinkedList. In a LinkedList, head is the first LLNode and tail usually represents the rest of the LinkedList linking directly behind the head. Thus, this class provides us with a more sophisticated way to modify lists. For example, if we want to pop an item in a common list, we can use the Python built-in method "pop" or "remove". But if we are working with a LinkedList,  we can simply let the head and rest to be rest.head and rest.rest, thus the original head is removed and then we can lind this new tail to a new head. Compared to "insert" or "append", we let the item which we intend to insert in to the list to be a new head of a tail, then link the modified tail to the original head. I would say, LinkedList focuses more on the relationship between each item rather than the whole list. In a common list,  we use index to control items but here, we have heads and tails and this head-and-tail depends on how you see it, which is more flexible, though I've been more used to list. I remembered we even saw a function to reverse a LinkedList, which is pretty cool with recursive calls. In LLNode class, the head-and-tail becomes current node and next node, which makes it more convenient to implement methods in a LinkedList since LLNodes are nodes in a LinkedList.

LinkedList is actually very useful, for example,  we can make a Stack class represented by a LinkedList so its original methods become more sophisticated. It's really blowing my mind. The lab about implementing methods in a LinkedList makes me reflect more on LinkedList, it was encouraging since it seemed I really got the hang of it.

week_7: Recursion

So midterm happened last week and I was late for like, at least 15 mins. I was suddenly awake in the morning right at 8:59 and had to rush to WB from Chestnut! (Mein Gott!) But it turned out not bad and it really was a relief! Hope the 'sleepover' thing doesn't happen to my final.

We've been working on the recursive functions since this course began and it totally reflects the 'laziness' in computer science, which we must master as CS guys. It calls it self inside in a clever way and since I've seen lots of examples, it really works especially when I understand clearly about what I'm gonna do with my functions. It demonstrates a sophisticated way of understanding. For instance, like what happened in lab #7, it's intuitive to write some function with while loop, which we learned in CSC108. But if we try to apply recursive to it, the whole function becomes cleaner and neater, which is quiet impressive. But at first I don't really feel like it since I have to trace it by hand and these recursive functions aren't something you can understand at first sight. Sometimes I feel like I would run into infinite loop and won't get out of it. But after practicing for some time, I think I'm getting used to it. Recursive functions, in particular, recursive definition of sets, a term in CSC240, are quiet enlightening coz they make best use of only a few lines of codes. I hope that I can see more examples in many different ways with the idea of recursive in this class.

week_6 Binary Tree

It's been a tiring week right before reading week with 2 midterms and a few quizzes to write and assignments awaits to due. Life just sucks sometimes, but it goes on and on without stopping, and I can do nothing with it, especially when I have 3 more midterms to write right after reading week.

This week we've been talking about this binary tree stuff the whole time, which is exactly the same thing we've been working on in CSC240. I guess it's gonna be quiet important point might be checked on midterm. There's really nothing I find worth mentioning in this slog coz it's just like comprehending  and memorizing. I must admit this tree is quiet magic. It can be expressed as a class in Python and we can get to every node in 3 different orders, which makes me thinking about organization of datas. Also, recursive has been used in almost every method like counting leaves. This tree must be quiet handy someday in the near future, midterm for instance.

Labs has always gone quiet smooth though, which is good. And I finally learned how to write a unit test in the right form.

Recently I feel like I weren't a CS guy but a math guy, which is weird. But I'm gonna stick on to CS I think. I've been thinking about taking summer courses, but is it sufficient to grasp all the stuff in a shorter time? I would go for some language classes rather than spend the whole summer typing code indoors, I suppose.

week_5 More recursive

This week we've seen more examples in recursive, among which, move_cheeese has been a great help to A1, where we're supposed to do a more complex one with 4 pegs rather than 3.( I decide never to start that late ever again! ) It took me quiet some time to figure out how it works and I found stuffs like recursive sometimes give me a hard time tracing them in my head. I tended to do all the things, i.e. finding best split point and getting all move sequence possible all in one function, which turned out a bad idea and thus I got stuck for, like 2 days, trying to figure out how n-k works for the case where n-k < n. But when I wrote a function computing best k, it's no longer a problem.

 Though I've been learning recursive for the past 2 weeks, it's still kinda challenging to figure out the best code using recursive. What's more, I really don't get it why those codes shown in class always have only one long, subtle sentence for the function body. Whatever, it's really not clear enough for me and I personally prefer not writing a full sentence.