I don't want to sound all cheesy and stuff but seriously it's been one heck of a ride in csc148. I can't believe we're almost finished this semester already. To be honest. Like really honest. Like not suck up honest (I swear to God), I've actually found the assignments to be really interesting to do. Most of them make me think outside of the box (like brain exercise. ugh exercise...). There are always so many ways to get something to work, but at the end of the day it all boils down to how fast you can get the job done.
Many people can tread such far paths to get something done, but the first commandment of computer science is to "Always be lazy". By this I mean doing something in the least amount of time/steps and not sitting on your couch munching on chips (Please don't hold me responsible if people start comparing pot bellies to determine who's the real master of computer science). In order to accomplish something like this, we first need to know what efficiency is.
Efficiency is the extent of which resources are used to accomplish a task. In computer science, this means memory and runtime. We always want to "be lazy", so we will always want to find a way to do something doing the least amount of work. This means we need to find the most 'efficient' runtime (least amount of time or steps to accomplish said task), while taking up the last amount of space. For now, we will talk about runtime, because it's the one we've been taught to control the most in this course.
We've encountered efficiency in our first assignment, The Tower of Anne Hoy, we had to come up with the most efficient algorithm to solve the puzzle. It was a relatively large portion of our mark, so my partner and I spent gruelling days pondering over what it was, drawing pictures and tracing code. In the end, we thought we found the most efficient way of doing it (17 steps on 6 cheeses and 4 stools), but our efforts were of no avail for games with larger number of cheeses and larger number of stools.
Efficiency is usually measured in the big-Oh of a function, which is really just a rough estimate on the upper bound of the runtime of an algorithm. For example, an algorithm that has a runtime of O(n^2) will quadruple in runtime when the list is doubled in size (because (2n)^2 is 4n). Most of the time we will want to use big-Oh when estimating the worst case of an algorithm. Big-Oh is an extremely important concept in sorting.
Sorting is a problem drenched in efficiency. People are always trying to come up with the most efficient way of sorting a list. Sorting is simply arranging a list into an ascending order, or in a particular sequence. So far we have encountered several O(n^2) sorting algorithms (i.e. bubble sort, insertion sort, quicksort and selection sort in their worst cases), and an O(nlog(n)) algorithm (merge sort).
The O(n^2) algorithms usually require double looping and the O(nlog(n)) algorithms usually involve dividing the list into two multiple times.
I'm going to dive into some deep logical explanation so if you don't want to read my long rambling of my thought process when determining big-Ohs just skip to the end of my example explanations (I HAVE MADE THE END CLEAR) :
For example, if a sorting algorithm divided a list into 1/5th of its length then linearly sorted them one by one, the algorithm would have O(n) traversal. This is because the list will always be divided into 5 sections independent of the list length, so it would have O(1). But afterwards, when linearly traversing each 1/5ths of the list, it would scale linearly and would have O(n). The overall runtime would be 5 times n (one n for each of the 5 times it traverses the list), but 5n is O(n), so in the end we would say that the algorithm is O(n).
As such, merge sort has an O(nlogn) runtime. This is because it will integer divide the list into two halves until each sublist has only one element left, this step will be O(logn). Following this, it will linearly sort each of these lists to make a larger list, and eventually combine them into the final list (O(n)). From this, we know that we will have to have log n for each n, which means the final runtime will be something like O(nlogn)
Another example, quick sort, has a runtime of O(nlogn) in the best case, if the pivot picked can efficiently divide the list into two at all times (dividing into 2 n times has O(logn) runtime) then linearly sorting it (multiplied together is O(nlogn)). In its worst case, it will have a O(n^2) runtime. This is because the pivot would only separate one largest element or one smallest element each time and that would equate to an O(n) run time. Then the overall runtime would be O(n*n) => O(n^2).
The O(n^2) algorithms usually require double looping and the O(nlog(n)) algorithms usually involve dividing the list into two multiple times.
I'm going to dive into some deep logical explanation so if you don't want to read my long rambling of my thought process when determining big-Ohs just skip to the end of my example explanations (I HAVE MADE THE END CLEAR) :
For example, if a sorting algorithm divided a list into 1/5th of its length then linearly sorted them one by one, the algorithm would have O(n) traversal. This is because the list will always be divided into 5 sections independent of the list length, so it would have O(1). But afterwards, when linearly traversing each 1/5ths of the list, it would scale linearly and would have O(n). The overall runtime would be 5 times n (one n for each of the 5 times it traverses the list), but 5n is O(n), so in the end we would say that the algorithm is O(n).
As such, merge sort has an O(nlogn) runtime. This is because it will integer divide the list into two halves until each sublist has only one element left, this step will be O(logn). Following this, it will linearly sort each of these lists to make a larger list, and eventually combine them into the final list (O(n)). From this, we know that we will have to have log n for each n, which means the final runtime will be something like O(nlogn)
Another example, quick sort, has a runtime of O(nlogn) in the best case, if the pivot picked can efficiently divide the list into two at all times (dividing into 2 n times has O(logn) runtime) then linearly sorting it (multiplied together is O(nlogn)). In its worst case, it will have a O(n^2) runtime. This is because the pivot would only separate one largest element or one smallest element each time and that would equate to an O(n) run time. Then the overall runtime would be O(n*n) => O(n^2).
~~~~~~~~~~~~~~End of examples explanations~~~~~~~~~~~~~
Sorting and efficiency is used in everyday life. If you're into online shopping, things must be kept sorted in order for you to find them easily. If you've just submitted in an assignment, the marks and papers must be kept in order for your professor or TA to easily find them, grade them, then correctly submit your marks back into MarkUs.
We are heavily reliant on sorting and efficiency, because wasted time is something we can never get back.
Nice explanation Cynthia. This is a much more, how you say, 'efficient' explanation of sorting and efficiency than my blundering tables... Btw what do you think of quick sort and merge sort? Which one do you like more? I always liked quick sort because I think it is more 'alive' since, as you said, it doesn't always divide the list equally. It is like a teacher with a student who has easy time with material sometimes and hard time with material other times, which in my opinion is an interesting student to teach. On the other hand, merge sort is a little robotic, as you said, it always divides the list into equal or nearly halves. No variability; similar to eating the same thing everyday... Yet then again, this quality of 'aliveness' can, as you said, make it more inefficient for certain inputs. What are your thoughts on those two algorithms?
ReplyDeleteWell, I much more prefer consistency when it comes to sorting algorithms. I feel like merge sort is a lot more consistently efficient. I understand where you're coming from about the 'aliveness', but say you had to sort something close to the worst case of both. I think I would pick the one that took the least time to sort. I mean like you could be using that time on something else, right? Like looking for the cure for cancer, eating chicken...etc...
DeleteI guess you're right. In computer science, the more 'consistency' (which I equate with 'blandness'), the better.
ReplyDeleteYeah, I can see what you mean. But finding better bland solutions can sometimes be quite a challenge!
DeleteI totally agree with your introduction! It makes me feel cheesy but I get a little nostalgic at the end of each year... and looking back on assignments (despite how stressful they were), they were a necessary challenge that felt great to overcome! Furthermore, as the year progressed, I found it even more difficult as the goal has become to not just solve a problem, but solve it in the most efficient way possible... which is an entirely different beast.
ReplyDeleteEfficiency was really difficult LOL. A lot of the time while I'm trying to work out a problem I'm always like "is there a better way of doing this? this seems waaay too complicated"...But the feeling when you do manage to find a better way to do something and it works out, man it feels good :D
Delete