Almost nobody implements a sorting algorithm at work. You call std::sort and move on. So the usual defence of learning them — “it builds fundamentals” — is doing a lot of unpaid labour in that sentence. Here is a better reason, and it is the one this post is built on. Three of the five algorithms below contain a reusable subroutine that shows up as LeetCode problems in its own right. Merge sort’s merge step is a problem. Quicksort’s partition step is four problems. And one character inside merge sort decides whether the algorithm is stable, which changes what you READ MORE
Tag: algorithm patterns
Binary Search Without a Sorted Array: Peaks and Rotations in C++
Every binary search in part one had a sorted array underneath it. Take that away and most people assume the technique goes with it. It does not — sortedness was never the requirement, only the most convenient way to meet it. This is the second of three posts on Joseph Choi’s binary search session deck. Seven problems here, in two families: three where the array rises and then falls, and four where a sorted array has been rotated. In both, something other than the sort order tells you which half to keep. As in part one, every listing was compiled READ MORE
Binary Search in C++: The Boundary Template and 10 Sorted-Array Problems
Binary search is the algorithm everyone knows and almost nobody writes correctly on the first try. The reason is not the idea, which is two lines. It is that every failure mode is silent: no crash, no timeout, just a wrong index. This is the first of three posts working through Joseph Choi’s binary search session deck in C++. Between them they cover twenty-two LeetCode problems, and they are split by the only question that matters — where does the monotonicity come from? This post takes the ten problems where it comes from the sort order, and sets up the READ MORE