WEEK 11: Sorting and Efficiency

    In general, a sorting is arranging collected elements or data in certain orders by comparing each other. There are many different types of sorting such as bubble, selection, insertion, merge, shell, and quick sorts. Each type has different efficiency, which is algorithmic efficiency as the size of the input grows larger, and is based on a number of elements to sort. Most sorts have algorithmic efficiency of either O(n^2) or O(n log(n)).

    Among the different types of sorting algorithms, the first three sorts: bubble, insertion, and selection consider as simple sorts. They perform differently, but they perform better on a small list or a list that is almost sorted, rather than a large list. A bubble sort is repeatedly swapping adjacent elements that are unsorted until the whole list of items in a certain order. An insertion sort repeatedly goes through all the items in an unsorted list each time, and inserts an item into its correct position. Similar as the insertion sort, a selection sort also repeatedly goes through a list to select an item according to its order, and place it in the correct position. All of three sorts have similar efficiency, O(n^2) on average, best and worst test cases except the insertion sort has O(n) on best case. As well as their stability is stable and their space is constant.  

    Unlike those three sorts, merge, shell, and quick sorts are more efficient on a list containing a large number of items in random order. As well as they do not use comparison, and are more complex algorithms. A shell sort compares elements far apart in the beginning, and then compares elements less far apart. At the end, it compares adjacent elements similar as the insertion sort. A quick sort divides the list of items into two sub-lists based on a pivot element. In one of the sub-lists, elements are arranged to be smaller than the pivot element, and in another sub-list, elements are placed to be larger than the pivot element. This process continues on the resulting sub-lists until the whole items are sorted. A merge sort is similar as the quick sort. It also divides a list, but it does not have a pivot elements. In the beginning, it divides the list into n sub-list with only 1 element. And then it merges a sub-list with another sub-list to produce new sorted sub-lists, and this process repeats until all the sub-lists are merges together and sorted. For these three sorts, their efficiency is O(n log(n)) on best case. For merge sort, it has O(n log(n)) efficiency on best, average, and worst case, but the other two sorts are different. The quick sort has O(n log(n)) on best case, but has O(n^2) on worst case. The shell sort has O(n^2), too, but on the average case, it has big o notation depends on gap sequence. The space complexity for quick sorts is constant, but merge sorts is depends on whether it deals with linked list or arrays.

    I have learnt about insertion, selection, and bubble sorts in CSC 108, so I was familiar with those three, but not with the other three sorts. I was confused by just looking at the codes of the three functions that I learnt in this course, but the link on the course website helped me a lot. The link explains what they are, and also shows the pictures of how they work. However, understanding big oh notation was hard for me and it is still hard. I also learnt about efficiency in CSC 108, but I did not fully get from that course, so I had hard time with big oh notation. So, I looked up about the big oh notation and how they are different on different test cases and on different sorting algorithms. As well as this week lab was little helpful to understand the concept. I should keep practice on it as I tried to understand the recursion. When I prepare for the final exam, I should focus more on this topic and binary tree.

Missing Weeks

From week 8 to 10 I learnt about a binary tree, a linked list and a binary search tree.

A linked list is a linear data structure containing elements. Each element contains a data and a reference to the next node. The first node in the linked list refers as head, and the last node points null. The advantage of a linked list is that the number of nodes in the list is not fixed, and can add or delete the node. However, it cannot directly access to the individual elements. To find a particular element, need to go through from the head and the reference until it reaches the element.

The binary tree is made up by nodes, where each node contains element, left and right references (or subtree). This tree has many terms. First, the node at the top is called root. Parent is a node directly connected from one other node. Children are an arbitrary number of nodes connected branched off from parent. The number of children has to be either 1 or 2. If a node does not have children, it is called leaves. It represents data in hierarchical form, and does not allow duplicate values, so it will be easier to find a certain element in tree structure.

The binary search tree is similar as the binary tree except a left sub-tree contains a number less than a root while a right sub-tree contains a number bigger than the root. Both sub-trees also have to a binary search tree. As similar as the binary tree, it is easier to find an element since elements in left sub-tree are smaller than an element in root while the right sub-tree contains bigger elements. It is also efficient on memory space, because it does not reserve more memory than it needs to. It can act as a list, so it can split, remove or insert an element faster.
In general, I think the computer science topics are hard for me to understand and apply knowledge to write a code. Most of time, I need to practice and go over what I did or learnt in labs or class to fully understand. I looked up the idea and practiced, so I think I can do it now, but I think I need more practices. 

WEEK 7:RECURSION

   Recursion is a useful method that calls itself. It breaks down a complicated problem into smaller part to solve some and to approach the problem easier. We have learnt and practiced this topic for few weeks but I am still struggling with the recursion. I thought I was able to use this method to write a function during labs. But I guess I was able to do because I was working with my partner. Whenever I work on a recursive function by myself, it takes more times to figure out the problem and the solution. I do not know if this is normal for everyone. Among many functions, concepts and topics learnt so far, I think the recursion is the hardest topic. I should keep practicing on it until I become comfortable with recursive function.