Grokking Algorithms

Chapter 4
 
 
I
 
 
Quicksort
You ca
n it two 640 × 640 boxes in there, and there’s some land still
let to be divided. Now here comes the “Aha!” moment. here’s a
farm segment let to divide. 
Why don’t you apply the same algorithm
to this segment?
So you started out with a 1680 × 640 farm that needed to be split up. 
But now you need to split up a smaller segment, 640 × 400. If you 
ind 
the biggest box that will work for this size, that will be the biggest box
that will work for the entire farm. 
You just reduced the problem from
a 1680 × 640 farm to a 640 × 400 farm!
Let’s apply the same algorithm again. Starting 
with a 640 × 400m farm, the biggest box you 
can create is 400 × 400 m.
Euclid’s algorithm
“If you ind the biggest box that will work for this size, that will be the 
biggest box that will work for the entire farm.” If it’s not obvious to you 
why this statement is true, don’t worry. It isn’t obvious. Unfortunately, the 
proof for why it works is a little too long to include in this book, so you’ll 
just have to believe me that it works. If you want to understand the proof, 
look up Euclid’s algorithm. he Khan academy has a good explanation 
here: https://www.khanacademy.org/computing/computer-science/
cryptography/modarithmetic/a/the-euclidean-algorithm.

---

55
Divide & conquer
And that leaves you with a smaller segment, 400 × 240 m.
And you can draw a box on that to get an even smaller segment,
240 × 160 m.
And then you draw a box on that to get an even
smaller
segment. 
Hey, you’re at the base case: 80 is a factor of 160. If you split up this 
segment using boxes, you don’t have anythin
g let over!

---

56