Sorting algorithms

This week, we continued the topic started last time. The big-oh notation. We studied the application of the notation in calculating the orders for various sorting algorithms. The sorting algorithms were explained to us using different sized coffee cups, which was a very nice technique to demonstrate the sorts in a practical way, allowing us to understand them better, rather than just looking at the code and trying to get it. Another advantage of doing it was that we could compare the times taken by each sort, and discuss about their orders easily, thereby coming to a conclusion on the better sort. A few types of sorting algorithms that we discussed were selection sort, quick sort, merge sort and count sort. Each of them used a different method and took different times to complete. Then, we compared them by their running times through a program, with varying size of the input. Selection sort lead initially, but as the size got larger, the factor of n² came into play and it started taking much longer time. Count sort and the built-in sorts were the long term leaders, but for extremely large inputs, count sort was better. The only reason why it is not used widely is that it cannot sort values in the input that are larger than the input size.

Other things going on in the curriculum are the upcoming fall break and the second term test. The fall break is an ideal time to study, as well as for procrastinating. The term test on November 13 will encourage some studying though. But, it’s a nice time to finish up all the incomplete work, and also relax a bit by not having to attend the university.