These past weeks we've been learning the types of sorting algorithms and how they would perform as the input gets larger. While there were the ones I was already already familiar with in csc108, bubble, selection and insertion sort, a few new ones were introduced. The new sorts were 'Merge', 'Quick' and 'Tim' sorts. The merge sort algorithm consists of breaking down the input list down to one element lists and merging the lists back into a new sorted list. The quick sort using a 'Divide and conquer' method, by picking a pivot, and using markers, splits the list into two, and then quick sort the two. Tim sort is the sort python uses, it's a hybrid sort of merge and insert.
All of these types of sorts have a best and worst case runtime, depending on the features of the input. For example, if the list was sorted already or if it was reverse order or if the list was sorted already. In class, we would also look at how the algorithm would behave when the input size changes; seeing how the runtime would grow. We called this Big-oh for simplicity's sake even though the. We would say an algorithm would be big-oh of 'something' which would mean the algorithm is growing 'something' for a particularly large input.
Other than that, I finished my second and last midterm of the class. I felt that I needed more time for the test. I think I could've finished it, if only I had a little more time.
-Tri Tran
No comments:
Post a Comment