Imagine dividing a 1,680 m × 640 m field into the largest equal square plots possible. You can mark out two 640 m squares, but a smaller rectangle remains. Instead of starting over, solve the same problem for that 640 m × 400 m remainder. The smaller answer also works for the whole field. section 4.1
That is the divide-and-conquer approach: reduce a problem to smaller versions of itself until you reach a case you can answer directly. It gives you a way to tackle an unfamiliar problem, not just a recipe for one algorithm. section 4.0 section 4.1
When trying it, ask two questions:
- What is the simplest case? This is the base case. For the field, a rectangle whose longer side is a multiple of its shorter side can be tiled directly. section 4.1
- How can each recursive call make the problem smaller? For the field, remove the largest squares that fit, then apply the same question to the remainder. section 4.1
Sorting by solving smaller sorts
Quicksort uses the same idea on an array. An empty array or a one-element array is already sorted. Otherwise, choose a pivot, put smaller values on one side and larger values on the other, sort those two sub-arrays recursively, then combine the sorted left side, pivot, and sorted right side. For example, [10, 15] + [33] + [] gives [10, 15, 33]. section 4.2
def quicksort(array):
if len(array) < 2:
return array #1
else:
pivot = array[0] #2
less = [i for i in array[1:] if i <= pivot] #3
greater = [i for i in array[1:] if i > pivot] #4
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
#1 Base case: arrays with 0 or 1 element are already sorted.
#2 Recursive case
#3 Sub-array of all the elements less than the pivot
#4 Sub-array of all the elements greater than the pivot
The Python implementation puts the two questions into code: return arrays shorter than two elements; otherwise, partition around a pivot and recursively sort both parts. section 4.2
Breaking a problem apart does not guarantee the same speed every time. Quicksort takes O(n log n) time on average with a random pivot, but O(n²) in the worst case. The approach tells you how to structure a solution; how you divide the work still matters. section 4.6 section 4.5
