Week 10: Assignment 2 (Part 2) and More Sorting

This week, the last assignment for the semester was completed, and we learned more about different kinds of sorting algorithms. 

Assignment 2 part 2: I liked this part much more than the first part of the assignment, because this time we actually got to write code for functions. Although I still enjoyed the design portion of this assignment (part 1), I generally enjoy the problem solving part of computer science more. My partner and I split up the 4 functions between us, so I was doing is_regex and regex_match. The weekend before it was due, I had spent A LOT of time on is_regex, going in the wrong direction. The approach I had taken was kind of an 'obstacle course' coding method: there were all these conditions that if the input didn't meet, the function would return False. At the end, if the input had survived that long then it must be a regex and the function would return True. Unfortunately, this proved nearly impossible, at the point where we had to do recursion on the inner regexes. On Monday in class we were given a hint, which was to take the opposite approach: check to make sure the string satisfies basic regex conditions, and then call is_regex on the inner (possible) regexes. This way, if the brackets/dots/bars were messed up, the recursive call would simply return False at some point. This took my code from over 40 lines and turned it into 10 clean concise ones. I feel that this technique is really important for coding when you're checking if input is of the right format: check the basics, and then assume it is of the right format and perform operations on it. If it isn't, eventually it won't be able to fake it anymore.

Sorting algorithms: This week we learned about two sorts: quick_sort and merge_sort. The interesting thing about quick_sort is that its worst case runtime is actually when the list is already sorted (or sorted in reverse). We can change this based on our choice of pivot however, in which case quick_sort almost runs as quickly as merge_sort. Merge sort is the fastest sort we've encountered so far (except for the built-in sort), with O(n lg(n)) run time. It is interesting to see how much recursion improves the run time of sorting algorithms: when these new sorts were tested against the ones we used in 108 (before we knew about recursion), they were significantly faster. The reason recursion improves it so much is that it allows you to repeatedly split the list in half and sort each half, using recursion. This splitting the list in half is what accounts for the log (base 2) n iterations of the algorithm. It will be interesting to see what other sorting algorithms there are that we haven't learned yet, and to see if there is a fastest one out there.

Good luck on the midterm everyone!