On Sorting and why you should attend classes
Back in my 3rd Semester i always used to wonder why i need to study so many sorting algorithms when we don’t use them anyway. I knew it was for us to “start thinking” but i never really applied it to my course of life.
Fast forward four semesters and it dawned on me while skimming through Skiena’s Programming Challenges
” You’ve quite possibly seen a dozen or more different algorithms for sorting data. Do you remember bubblesort, insertion sort, selection sort, heapsort, merge sort, quick sort, radix sort, bin sort, Shell sort, in-order tree traversal and sorting networks? Most likely your eyes started to glaze by the time you made it halfway though the list. Who needs to know so many ways of doing the same thing, especially when there already exists a sorting library function included in your favourite programming language?
The real reason to study sorting algorithms is that the ideas behind them reappear as ideas behind algorithms for many other problems. Understand that heapsort is really about data structures, that quick sort is really about randomization, and that merge sort is really about divide-and-conquer, and you have a wide range of algorithmic tools to work with”
It only then after some after-thought, that i found these as proof for what he said
The MRQ problem
Typical Divide and conquer, infact a senior of mine solved it using an algorithm that was very similar to merge sort.
Finding the kth smallest number – Uses a modification of the quick sort algotihm
Sigh, i wish i had listened in class.