During weeks 10 and 11, we explored various types of sorting algorithms, and their efficiency. The 2 sorting algorithms we focused on were quick sort and merge sort. Pretty cool names for sort, huh? Although I do like the name of bubble sort alot better. Because bubbles. So how do they work?
Quick sort is an interesting sort that implements the idea of a pivot. So the way the algorithm works is we set an element from the list to be our pivot (what's pretty neat is that in some implementations of this sorting algorithm, the pivot is chosen randomly, others have a formula to pick one. I think it's cool that people can approach this algorithm in various ways). Now what we do, is we reorder the list so that all elements in the list less than the pivot go before it, and all the elements greater than or equal to the list go after it. We do this recursively with the left side of the pivot and the right side of the pivot until there the list is sorted. It's a pretty wicked sorting algorithm in my opinion. So where does efficiency come into play? Actually, let's take the time to talk about it for a bit.
When it comes to efficiency, programmers often focus on the worst case. Wait, what? Worst? I thought we were aiming to be the very best, that no one ever was? Nope. We're aiming for the worst. To become the best. Get it? Haha. People are concerned about the worst case because it is important to know how much time one requires in the worst case to finish an algorithm. If we know the worst case for an algorithm, then we can work with it appropriately. One notation we use to describe run time is the Big O' notation. We say things like this algorithm has a runtime of O(n^2). What does this structure mean? The function within O is the runtime in proportion to the size of the data, n. So O(n^2) means that the runtime is square the size of the data.
Back to quick sort, what is it's worst case run time? O(n^2). We explored this idea in class; the pivot would become the first item in the list, and the list was already sorted. This would only split the pivot from the rest of the list, and not into 3 separate items (left, pivot, and right list). So that would mean the function had to run through n items, then n-1 items, then n-2 items. Adding that up, we get the familiar algorithm of 1/2(n-1)(n), which becomes 1/2 (n^2 - n), and when you take away the constants, you get n^2. Hence, O(n^2) runtime.
The other algorithm was merge sort. Now this is some fancy stuff. Divide and conquer style sorting, heh. The list split into 2 parts, and it recursively does that until the list size is 1, then the 2 parts that were split are sorted. It does this recursively, sorting at the smallest list size level, and working its way up. I think it's another cool sorting algorithm, that's pretty damn clever. So what about the efficiency of merge sort, more importantly its worst case run time? Well, splitting the list in half, doubles the size of the sorted sections, (log n), and then it has to pass through n amount of items (length of the data set), so the big O is O(n log n).
This is my last slog, so thank you all for taking a peek. See you around!
