Week 11: Sorting efficiency

A sorting algorithm is an algorithm that puts elements of a list in a certain order. We've learned various sorting methods in this course and CSC108, but what's the fundamental difference between all these methods? And why does it matter?

In my opinion, it is the sorting efficiency.

But why does the sorting efficiency matter?

No matter what sorting algorithm we choose, an expected result will be generated  as long as we choose a correct one. However, a more efficient algorithm will save a lot of running time and  it is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists.

For example, we've learned Bubble sort and  selection sort in csc108. Suppose we are asked to sort [5 6 8 2 14 24 16 1] using these two methods.
Selection Sort:
[{5} 6 8 2 14 24 16 (1)] unsorted array. Find the smallest element () in array and swap with first element {} of unsorted array [].
1 [{6} 8 (2) 14 24 16 5]. Do the same process again.
1 2 [{8} 6 14 24 16 (5)].
1 2 5 [{(6)} 14 24 16 8].
1 2 5 6 [{14} 24 16 (8)].
1 2 5 6 8 [{24} 16 (14)].
1 2 5 6 8 14 [{(16)} 24].
1 2 5 6 8 14 16 [{(24)}].
1 2 5 6 8 14 16 24. Finaly got the Sorted array

Bubble Sort:
In bubble sort elements are compared with just next element if the first {} is greater than second [] then swap.
{5} [6] 8 2 14 24 16 18 [no swapping move forward]
5 {6} [8] 2 14 24 16 18 [no swapping move forward]
5 6 {8} [2] 14 24 16 18 [swapping move forward]
5 6 2 {8} [14] 24 16 18 [no swapping move forward]
5 6 2 8 {14} [24] 16 18 [no swapping move forward]
5 6 2 8 14 {24} [16] 18 [swapping move forward]
5 6 2 8 14 16 {24} [18] [swapping move forward]
5 6 2 8 14 16 18 24 [swapping move forward first phase over again starts with first index]
{5} [6] 2 8 14 16 18 24 [no swapping move forward]
5 {6} [2] 8 14 16 18 24 [swapping move forward]
5 2 {6} [8] 14 16 18 24 [no swapping move forward]
5 2 6 {8} [14] 16 18 24 [no swapping move forward, there is no further swaping in the phase start next phase]
{5} [2] 6 8 14 16 18 24 [swapping move forward]
2 5 6 8 14 16 18 24 Finaly array is arranged in ascending order.

Obviously, selection sort is more efficient. And here, the input size n is small. If we're asked to sort an array of larger size, then the difference will be huge as well.

Talking about sorting a sample of large size, we need to know the big O notation. The first time I learn big O notation was in my CSC240 class, which is a course about computation complexity.  "In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in the input size."(Wikipedia)

 

But essentially, it's a math topic, and it describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.  Here, the argument of the function is the input size and the function describes the corresponding running time. 

Let's show it graphically.

When input size n is small, though the efficiency matters, it is not very important. However, when n is large it matters a lot.  Most real worlds problems we are facing have a very large input size, and that's why we need efficient algorithm. 

Week 7: Recursion

Since the beginning of this semester, recursion has become the most important concept for this course: we are talking about it at class, practicing it in lab and writing codes using it basically for everything.

But what's recursion?

By definition, "recursion is the process of repeating items in a self-similar way" (from Wikipedia). But, in my opinion, I usually just think it as another name for induction (since it works similarly with induction, and I know they are different). we construct the base case (or cases), and then define certain rule on how to construct other cases based on the base case. In my opinion, so far in this course, mostly, we use recursion for two purposes: construct a data type (such as tree) and define a method/ collect data on a recursively-defined class/ data type.

Personally, I wouldn't say recursion is hard. In my opinion, it sometimes becomes a problem is because that it is a comparatively new concept and we are still learning it. But, in fact, it is not a new concept. However, we did not learn it from CSC108. We were exposed to this concept in different mathematics classes (calculus, math concept) and CS courses which focus on computation complexity. In my opinion, induction, structural proof and recursion are essentially same. All we need to consider is that find out what's the base case (or cases) and rules to construct cases. And to solve these two questions, there are a few methods.

The first one is drawing a processing diagram. The only path that lead to the output is the simplest case. If it's not, we call recursion on it to simplify it until it reaches the base case. The diagram is very useful tool when you start working on recursion (in my opinion), since it's straightforward and simple. But, it takes time to finish the picture. The second way is better than the first one, since it's more abstract and it saves time. It's to write down the mathematical function, which is the essence of the code (sometimes the math function is same with the code). We've met an example, which appeared on the handout of A1 (for Hanoi tower).

As I mentioned above, recursion is used everywhere in this course, for example, A2. In my opinion, tree is a perfect example to demonstrate recursion, because we construct tree by recursion (base case: root node) and almost every tree method needs recursion (since tree is recursively constructed). More specifically speaking, the basic element of a tree is a node, and everything is based on the node. For example, if we are asked to define a tree method, first we need to ensure it works for the root node.

These are what I think about recursion.

Week 6: Tree

So this week we learned what's tree, how to construct a tree recursively and how to use tree to store data.

Generally speaking, tree is an abstract data type that simulates a hierarchical tree structure, with a root value and sub-trees of children, represented as a set of linked nodes. Also, a tree can be defined recursively as a collection of nodes (starting at a root node), where each node has a value, together with a list of "children" nodes. Tree is very useful and convenient, since a tree can be analyzed mathematically both by nodes and as a whole.

Recursion is what we use to construct a tree. Since every tree is constructed by nodes (or sub-trees), we can set the root node as the base case of the tree. Thus we define what a node is in the __init__ function. And when we build a tree, we can keep add new nodes as children to the root node. Since the tee is constructed by recursion, when we need to get all data from the tree, we need to use recursion to get the data, and thus we have pre-order, in-order and post-order (we get data node by node). Similarly, when we define tree methods, recursion is used (since every method is supposed to work on a tree which's built recursively).

In my opinion, tree its self is not a challenging concept, but the recursion under it is. It's not easy to point out what's the base case and how to build recursion step when I first met the concept. However, I found it very helpful to use structural proof (what I learned from CSC240) when I work on recursion problems. Root node is the base case, and the children are constructed by induction ( recursion) steps. And tree methods are supposed to work on the whole tree (both root and children). This is super similar with the structural proof ( Prove a proposition works both for the base case and the induction), but the difference is that this time we are not asked to prove certain arguments, instead, we are asked to find a method which works for the entire. However, the idea is same.