It takes more to put a list in order than it may seem. This week we spent time covering different kinds of sorts, their implementations and strategies and how efficient they are. I suppose you can say sorting was the key topic, but I think it is more of an example of the more general concept of algorithm efficiency. By analyzing the steps involved in each search algorithm, particularly the number of times the algorithm had to look over or modify the list, a comparison could be made between them. Abstracted to a n-element long list, the comparisons could be read out as complexities for each algorithm, to show why a particular one worked better than another.
Abstraction aside, generally merge and quick sorts followed by insertion sort were the preferred ones as they executed the fastest, and typically bubble sort was the worst. In some cases, such as the list being reversed, this did not hold true. Though we did not go over it in detail, I looked into Python's built-in list sort, timsort. It appears to be a combination of merge sort and insertion sort, calling the merge sort initially to break up the list into smaller ones at which point calling insertion sort on them is quick and easy. It then reconstructs the sorted list using the merge sort functionality.
Lab this week was also focused on this, timing the various sorts for various cases and coming to the conclusions above. It also went into looking at ways of making functions more efficient, by storing repeated calls of length, for example, as variables and just using the variables as needed cutting down on execution time by the number of lowering calls.
No comments:
Post a Comment