Week #8

Thoughts

This week we mainly talked about some more big-Oh.
Big-Oh is one of the most important concept in computer science. And it is very important in computer science.

Despite all that, this week I'm going to talk about sorting algorithms. And here are the algorithms on Wikipedia:
Quick sort
Heap sort
Merge sort
Intro sort
Insertion sort
Selection sort
Bubble sort
Odd-even sort
Cocktail sort
Cycle sort
Merge insertion (Ford-Johnson) sort
Smoothsort
Timsort
...

But I found one sort Spaghetti sort is very special because it uses linear time O(n). In short, the algorithm is if you have a set of natural numbers, then for each number x in the list, obtain a rod of length. Once you have all the spaghetti rods, take them loosely in your hand and lower them to the table to make them stand upright. Then for each rod, lower your other hand from above until it meet with a rod, and that rod is clearly the longest. Remove this rod and move it into the the front of the output list. Repeat until all rods have been removed. Since the time of preparing the n rods of spaghetti takes linear time, and lowering the rods on the table takes constant time, the whole process takes linear times, O(n).
However, this algorithm is impossible in actual programming. It requires n processor to process the lowering action. But this method is useful in our daily life, for example sorting the length of pencils.