This one's a bit ate but last week, we started looking into Big-Oh and the run time of different sorting algorithms on different sizes. He first introduced the quick sort which I learned in high school how it worked but never programmed so it wasn't to difficult. It more or less chooses a value in the list and sorts all the values smaller than it to its left and all the values bigger than it to the right. This recursively calls itself until eventually, you are left with a single value list and therefore "sorted". Merge sort works in a similar way but instead of separating the smaller ones and bigger ones to each side, you just split the list into halves regardless. After it is broken down to its single value, the individual values compare themselves to one another and arrange themselves in a new list depending on which is smaller. Both sorts have a run time of about nlogn in their best case scenario where n is the number of values in the list but the problem with quick sort is that if the "pivot" you chose doesn't split the list up into 2 equal sizes, the run time is actually worse, going all the way to n^2.
Anyways that's about all I wanted to talk about for now, spending some time now finishing up making my cheat sheet for Wednesday's term test... hopefully goes well. I'll probably do a more detailed summary of what we've done sometime later this week.
No comments:
Post a Comment