Sorting and Efficiency

During the last few weeks we learned about varies sorting methods and their running time. The methods that are new to me are count sort, quick sort and merge sort.I learned that the idea about quick sort is to choose pivots, and so the list is divided into two parts. Then use quick sort to move the objects smaller than pivot recursively to the left of the pivot, and larger object to the right. The run time of quick sort is O(n log n).

Merge sort keeps dividing the list by two and obtains n sublists, each contains one element. And it keeps merge the values into new sublists. Merge sort is one of the O(n log n) sorting algorithm and has a worst case run time of O(n logn). It's faster than quick sort's O（n^2). But it takes more space than quick sort. 

In the lab this week, we compared these two algorithms with selection sort, bubble sort, insertion sort and python's built in sort(tim sort). It turns out that those O(n log n) algorithms(quick sort, merge sort and python's built in sort) are significantly faster than other algorithms when dealing with large inputs. Quick sort is fast for best case and normal case, but is slower than the merge sort for the worst case. Python's built-in sort is the fastest in most of the tests.

First Part of A2

In discussion of A2 me and my partner had some split in opinions. He thinks that the children should be a list containing two regexes or strings. And I think that there should be children1 and children2, both as inputs. After that we checked several questions on piazza and decided to use my partner's idea. We found examples extremely helpful. It's hard to come up with examples but after that everything is pretty easy. So we will finished that today and hopefully there's no more problems.
Well what I also found hard:

• to understand what the program __repr__ returns is kind of difficult for us. We have to check the piazza to decide whether or not to let it return exactly same thing with the input value.
• to use property to make the symbol and children read-only.
• to use format to write the __repr__ method. it turns out to be easier to write but harder to think.
• to communicate with partner--- actually more important than come up or writing down codes.