Divide and Conquer Algorithms Using Swift

One part then another!

Image for post
Image for post
Photo by Becca Tapert

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!

Image for post
Image for post

When we start we look for the element at the middle place of the array (position 3, element 4).

Image for post
Image for post

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.

Image for post
Image for post

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).

Image for post
Image for post

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].

Image for post
Image for post

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store