Chapters 3-4 of The Algorithm Design Manual
If last week was about building blocks, then this week we’re making buildings.
After finishing the section on data structures with Binary Search Trees and Hash tables, Skiena moves on to sorting – the mother of all computer science problems.
Here’s Skiena’s Take-Home Lesson on the power of sorting:
Sorting lies at the heart of many algorithms. Sorting the data is one of the first things any algorithm designer should try in the quest for efficiency.
Sorting is the basis of other more complex algorithms because once a set of items is sorted, many other problems become easy.
I really enjoy seeing ideas in this book build upon each other. Data can be organized into data structures. Data structures allow for sorting. Sorting allows for even more complex algorithms – like searching and comparing – to be more efficient.
With that understanding, I now more fully appreciate the beauty of an efficient algorithm. Beneath the code lies the enchanting allure of perfection – nothing can be added, changed, or removed. All the components build on top of each other – balanced as if on a tightrope. The ideal data structure chosen so that the clever sorting algorithm can be performed so that an immense amount of data can be efficiently and flawlessly manipulated.
Finding the perfect algorithm is like looking into a program’s soul and finding Truth.