Sorting and Effiency

In CSC108, we were introduced to three kinds of sorting algorithms, insertion, bubble and selection sort. Again at the end of the CSC148 semester, we learned two more sorting algorithms, quick sort and merge sort. A sorting algorithm is an algorithms that puts elements of a list in a certain order. In the following, I am going to talk about various kinds of sorting algorithms and its efficiency. In addition, we usually use different big-oh notations to express the complexity of each algorithms. 

Quicksort is something new to me, but after compare the running timing for 1000 item list, it turns out that it is a very efficient sorting algorithms. By using quicksort, we usually find a good pivot so that we can compare the items after the pivot. If the item is larger, we put it in front of the pivot, and vice versa.
In most cases, we choose the first item of the list as a pivot, and repeat the quicksort until the list is sorted. This kind of algorithm is usually used for large size of data. Its best case complexity is o(nlogn), but worst cases is o(n^2).
Merge sort is different, it splits the list into half, sort the two halves, and merge the sorted list again. By using the recursion, we can sort the whole list using this technic. The whole process remains the same no matter what list is given so that its complexity is o(ologn) for all cases.

Insertion sort works by moving the next item to its proper position in the sorted part of the list at beginning. This sorting algorithm the most basic algorithms but not very efficiency. Its complexity is o(n^2) for worst cases.
Bubble sort works by going over the list and place each item to its final position. It compare each item to the whole list and swap the one after it so that after each iteration, the final item must at the right place. Despite its worst complexity is the same as insertion sort and selection sort, bubble sort is the most inefficient sorting algorithm according to lab10's analysis.

Binary tree sort is very similar to the merge sort algorithms, since the structure of a binary search tree provided a good path for sorting. In a BST( binary search tree) node, the left children must be less than the root, mean while, the right children must be larger than the root. Under this condition, to sort the list, we just need to compare half of the items in the list. Its worst complexity is o(nlogn) just as merge sort.

Selection sort selects the smallest remaining item repeatedly and puts it to the proper position it belongs. This algorithm have the worst complexity o(n^2) because for each item in a n size list, it has to go over the whole list to find its position as well as its best complexity. It is not very efficiency.

Regular Expression II

On the second part of the Assignment Two, we were required to write four module level functions. The first one is_regex, returns True if a given string s is a valid Regular Expression. When we first encountered the problem, we thought it was a piece of cake, until we realized that there were at least six different conditions we need to consider. The code was finished in about 80 lines, but it was a little bit messy. The second function is all_regex_permutations, returns a list of possible valid regular expressions that a given sting s and its permutations can be. The difficulty was mainly on part one since we already have some code from the Professor during the lecture that deal with string permutations. All we need to do is generating all the permutations and checking which of them are valid expressions. The third one is regex_match, which is also the hardest one to implement. It returns True if the given string s matches the given regular expression r. The intuition was similar to is_regex, however, there were some minor details that need to be noticed. The last one was to build a regex tree when giving a valid regular expression. It was not that hard if you can finish the first three.

Regular Expression I

Over the last couple weeks, we were working our ass off on the second assignment of the term, which is about the concept of regular expression. According to Wiki, regular expression is a sequence of characters that forms a search pattern, mainly for use in pattern matching with strings, or string matching operations. Our tasks were in two parts, the first one was simply straight. We were asked to write various classes for different combination of regular expressions. The simplest form of a regular expression is a single string of either 'e', '0', '1', '2'. Furthermore, we can add as many of '*' (stars) as we want at any of regular expression to form a new regular expression. Also, we can use '.' or '|' to combine two different valid regular expressions to form a new one. Basically, all we need to do is to write a parent class for the single regular expression, and inherit all the features to create children classes. The reason we can do this is that the regular expressions can be presented in the form of a tree structure. We did not run into any trouble when finishing the first part, but after seeing the second part, we realized it might be a big challenge. 

Recursion

Half way through the term and we are exposed to more and more recursive structure design in the course. Recursion is the process of repeating items in a self-similar way. A recursive function that we are talking about in python, is a function that executes the function itself repeatedly until a certain constrain is met. We have seen a few recursive structures so far such as 'stacks', 'nested list',  'linked list' and 'tree, those we usually called ADTs. Recursion is used widely in all these abstracted data types to get access from them.
The most obvious reason why recursive function works in such a data type like 'nested list' is that the list itself contains more lists, and each of them may contain more and so on. We can always use for loops and if statements to write functions on them, nevertheless, the use of recursion would be more wise. By using the recursive structure, all we need to consider is that the most simple senior and let the recursive function handle the rest by itself. When you using the recursion, not only your code becomes much clearer and simpler, but also it makes you looking like a pro!