Divide and Conquer Algorithms Using Swift
One part then another!
Difficulty: Beginner | Easy | Normal | Challenging
This article has been developed using Xcode 12.1, and Swift 5.3
Prerequisites
Some knowledge about recursion would be useful: article here
Terminology
Algorithm: A process or set of rules to be followed
Divide and conquer: A problem solving method that works by breaking down a problem into two or more sub-problems which ar ethen combined to gice a solution
Subproblems: A problem whose solution contributes to the solution of a larger problem
What is divide and conquer? Take a look at the following video, or read on!
What is divide and conquer?
Divide and conquer is a way of solving problems. In everyday English we even use the saying “divide and rule” as the policy to maintain control over subordinates by encouraging dissent between them. Divide and conquer is similar, but we attempt to create easy to solve problems that then go back to solve the original problem we intented to solve.
The divide and conquer strategy
- Divide the problem into smaller subproblems
- Conquer the sub-problems by solving them independently
- Combine the results of conquering the sub-problems together
Binary Search
Binary search is probably the most common introduction to the divide and conquer strategy. For a full explanation (in Swift!) take a look at this article. An important prerequisite is the input array is in order.
The following array [1,2,3,4,7,8,9] is going to be searched for the element 2: Note that it is clear on first glance that 2 is in the array, however we will follow the steps to find the element!
When we start we look for the element at the middle place of the array (position 3, element 4).
Since the element we are looking for is less than the middle element (2<4!) we know that the result is on the left hand side of the array (0..2) — so we no longer need to consider the upper half of the array.
We look at the middle element, and it is the one we are looking for so we are done!
One nice implementation of this is shown below, including the testing for the binary search:
Merge Sort
A merge sort is a relatively complex sort, yet is highly efficent (at least compared to bubble sort).
This algorithm makes it clear that we combine the resultant sub-problems into the eventual result.
Quick Sort
Some say that quick sort is quick to order a list, but slow to understand. I disagree!
Here is how the algorithm can work on a sample array of [5, 2, 3, 4, 1].
Once again the algorithm works in a divide and conquer fashion:
* Divide the problem into smaller subproblems
* Conquer the sub-problems by solving them independently
* Combine the results of conquering the sub-problems together
Conclusion
By breaking down a subproblem into solvable subproblems we effectivley make a problem easier for humans to understand, but also make code more maintainable and usable for the future.
If you’ve any questions, comments or suggestions please hit me up on Twitter
