Week 11: Penultimate Sorting Extravaganza

Let's take a trip down sorting lane, shall we?

This week, we learned about the different types of sorting methods we can use in Python (and other computer science languages) and why some of them should never be used *coughbubblesortcough.* It was actually quite interesting to go in-depth and see exactly how some of the sorting methods worked. And now, I'll basically regurgitate that info but also provide cool gifs (or not, they don't seem to work)! Yay.

Bubble Sort

Oh boy, here we go.  Bubble sort goes through the entire list and always places the largest item at the end of the list, causing it to have a worst-case runtime of O(n^2) which is not good. While there are some ways it could be faster, such as having to check only once if the list is sorted, seeing the times tower over the other ones reminded me that if I have to, not to use bubble sort.

Insertion Sort

I personally like insertion sort, though I can see why some people don't really like it. It just accumulates a list as it goes along, plopping the end item where it needs to be. Simple! It's usually better to use insertion sort when the list is nearly sorted since there's little overhead.

Selection Sort

Selection sort should be used around the same number of times as bubble - close to zero. It is just sloooooooooooow. It goes through the entire list multiple times and builds it from the smallest up. Please don't use it.

Shell Sort

Based on insertion sort. Very good for smaller nearly sorted lists. A+.

Merge Sort

Ah yes, merge sort. This method splits the list to be sorted into a bajillion pieces, sorts those, then smushes them together bit by bit and sorts them again. Pretty cool, to be honest.

Built-In Sort

The last sort method I'll mention. Please use this one. It's so so fast and absolutely destroys the other methods in tests. It's actually a hybrid method based on insertion sort and method sort so it's pretty much magic.

All in all, it was quite fascinating to see how the timing of these methods went up as list sizes increase, through charts and other methods, and also to perform Big-O analysis on them. Hopefully I'll be able to delve into them more in the future.