This is the fourteenth day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

Hi there. In the last few chapters we’ve talked a lot about data structures like lists, sets, dictionaries, and so on, and we’ve talked a lot about sorting algorithms and search algorithms, but today we’re going to talk about divide and conquer, which is neither a data structure nor an algorithm, but you can think of it as an idea, as a way of solving problems.

Divide and conquer

  • Divide and conquer is a method in algorithm design.

  • It divides a problem into smaller problems similar to the original problem.

  • Solve small problems recursively, and then merge the results to solve the original problem.

  • The three steps above are the general steps of divide and conquer, all divide and conquer ideas are these three steps.

Scenario 1: Merge sort

Merge sort is one of the algorithms that we talked about earlier, and it’s designed with this idea of divide and conquer.

  • Split: Split an array down the middle.

  • Solution: merge sort two subarrays recursively.

  • Merge: Merges ordered subarrays.

Scenario 2: Quicksort

The idea of divide and conquer is also used in quicksort.

  • Divide: select the base, divide the array into two subarrays according to the base.

  • Solution: Recursively sort the two subarrays, then continue to divide the subarrays until the array is of length 1, at which point the recursion ends.

  • Merge: the last is the merge, first the array length is 1 to merge, in the two merged array merge, until all the array merged into one array.

conclusion

We can see the above two scenarios, is it not a divide and conquer? You take a big problem, you divide it up into smaller problems, you solve the smaller problems, you merge the larger problems, so these two sorting algorithms are typical applications of the idea of divide and conquer.

End~~~