Week 10 more on sorting

My handwork from last weekends paid off in letting competing A2 in advance. Though I haven't understand the codes for permutation fully, utilization is sweet.

Nevertheless, I still benefit from Monday's class in finding a significant flaw in my code. An insight in regex_match when it's used on a StarTree is that s is supposed to be a concatenation of si where every si match r. Initially, I only picture the simplest case with a number flowed by *. Then, I realized it could also be (0.1)*, which will watch every string that have a multiple copy of "01". Still, this part is tricky and I couldn't have done it without Danny's hint, which is to think of s as a combination of s1 and s2, where s1 matches r and s2 matches the rest of r+*. Computer science really requires the rigorous consideration of matters.

In addition, we are introduced two new method of sorting, which are considerably more efficient.

Quick sort: as the name tells, i think it's the most efficient sorting algorithm we get to know so far. The main idea here is to pick out a pivot and divide a list into halves with the first half containing elements smaller than the pivot and the second half containing elements larger than the pivot. Repeating the steps on the two lists leads us to the base case where there is only one element. In conclusion, to divide the list till the smallest unit requires log n steps. Meanwhile, after each division, we have to do a thorough comparison throughout the whole list with the pivot. So altogether, quick sort requires n* log n steps. Interestingly, we later modify the codes to let it choose a random pivot in the list. Picture a scenario where the list is in reverse order, we starts with the first element every time. The rest of the list are all smaller than the pivot, thus, the whole process would take up to n^2 times, which is similar to insertion, selection and bubble.

Merge sort: This is a tough one. It takes me a while to understand it. Starting from the basic, merging means taking two already sorted list, choose the smallest items between the smallest respectively. And take it out to be the very first item of a new list. Merge sort also shares some of quick sort's ideas in that they have the same general structure to divide a list into halves and also the same base case. One difference is, though, merge sort always split from the middle while quick sort can pick a spot to split. Tracing backwards, the most tedious scenario merges every couple of number together, which takes n comparisons. To sum up, merge sort also have O(n log n).

From this week's reading, here is a useful note on insertion:

 Shifting versus exchanging is also important. In general, a shift operation requires approximately a third of the processing work of an exchange since only one assignment is performed. In benchmark studies, insertion sort will show very good performance.