Tutoring Section 12: Sorting
Comparison Based and Counting Based Sorts
This is our last quiz section! Today we will be going over one of the most commonplace operations: sorting. There are a diverse set of algorithms to sort. We generally can bin them into two classes: comparison based and counting based sorting. Comparison based sorting is the most intuitive. We will be comparing elements with each other to create a sorted collection. The lower bound for comparison based sorts is roughly O(Nlog(N)) where QuickSort and MergeSort are normally the most used and considered as efficient. Another class of counting is Counting where we will be using the counts for different groups of element. The most used counting based sorting are MSD and LSD Radix Sort whose runtimes depend on the number of passes it ought to make and the count sort per iteration. These are extremely powerful tools that when used a correct base/radix, can obtain a linear runtime.
Lastly, I really wanted to congratulate you all for almost being done with the class. I am certain it was a stressful experience, but you got through it. I hope this was a fun and educating summer that will encourage you to start even cooler projects with the tools you gained. Hopefully, I will see you all again at some point. Let’s not act like strangers.
Resources