This week we covered various kinds of sorts. Some of them include selection, quick, merge, and tim sort. Of the sorts mentioned, we go from slowest sorting time to fastest respectively. Reasons for this were analyzed in class, mentioning how selection sort iterates n time to see what needs to be swapped, then another n times to swap. This results in O(n^2) time, as opposed to merge sort which cuts the list in half each time, then joines them back together, the join in itself is about n times, but the splitting is log(n), yielding a combined time of n log(n) time. Now we just observe these sorts based on their strict algorithms that do the same job yet in a different way, so why not combine all these sorts to form a gigantic one that does the job best in certain scenarios? Well that is the definition of tim sort, made specifically for Python.
Finishing up BST's we covered deleting from a BST and forming linked lists out of them. This was fairly challenging because creating the Linked List nodes required you to remember that once an object is created on the stack in python, it stays there until the code is done with it, so if you create a linked list node in the call, it is that object that will be within the prior. This was a key component to solving the lab and caused great pain for my partner and I to solve. Other than that BST's were fairly straight forward and I can see great applications of this being to store a list of contacts or numbers where indexing is crucial.
No comments:
Post a Comment