I have just read a chapter about sorting. I am now writing down everything I remember. Do not read this just yet... It is not edited, I haven't yet gone back to fill in holes in my understanding. This is to prime my brain to remember shit.
Sorting
-
Many algorithms use sorting as a building block.
-
To understand these algorithms later on requires an understanding of sorting.
-
In general, we study sorting on numbers, but we can sort anything provided we can define a pairwise comparison operation between two elements.
- As in, if we can define a method that specifies whether $a < b$, $a > b$, or $a = b$ for any type or value of $a$ and $b$ then we are golden.
-
There are five main algorithms that I remember for sorting:
- Naive sort (idk)
- Insertion sort
- Merge sort
- Quick sort
- Bucket sort
-
I don't remember the first sort
-
I barely remember insertion sort
-
Merge sort
- NOTES: This is a Divide and Conquer Algorithm (problem is reduced recursively into smaller problems of the same type)
- ABSTRACT: Split array in half, sort each half, merge results together recursively.
- THE METHOD: We split an unsorted array into two halves, recurse on each half.
- When we reach one element arrays, we say they are sorted.
- We then apply a merge operation on both of the sorted arrays defined as such:
- compare the top-most elements of ea. array (they are in sorted order) using our comparison function.
- grab whichever element wins based on the way you are sorting and repeat for the rest of the elements until both arrays are done.
- repeat until you only have one array
- DONE!
-
Quick sort
- NOTES: This is a randomized, expected-time algorithm (we expect it to perform well in most-cases (AND IT DOES! (usually)))
- ABSTRACT: Same as merge sort, but with explicitly chosen median element called the pivot.
- THE METHOD: We pick a random element and call it our pivot $p$.
- We then segment our array into three parts, before the pivot, the pivot itself, and after the pivot.
- When we reach one element arrays, there is only one possible pivot and we call it sorted.
- We then merge the arrays together in the same way as merge sort placing these sorted arrays before or after our pivot based on the comparison operation we define.
-
Bucket sort
- NOTES: This one is intuitive. Assumes your input is random (by random I mean evenly distributed across the distribution)
- ABSTRACT: Make $k$ buckets for $n$ items on some property of the input. Sort ea. item into one of these buckets. Nest buckets as you see fit.
- THE METHOD: Do a linear scan through all items and create buckets. If we are working with names, we might have 26 buckets one for each letter of the alphabet.
- On your pass, put each item into its respective bucket. If multiple names fit into one of the buckets, you can optionally nest buckets. as in:
A B C ... Z AA BE, BR CA ... ZO Aaron Ben, Brian Carter ... Zoey