Divide and Conquer in C++

Divide and conquer is a powerful algorithm technique used in computer programming. It involves breaking down a problem into smaller, easier to solve subproblems, and then solving those subproblems. This technique is particularly useful in sorting and searching algorithms, such as quicksort and binary search. In this article, we will discuss how to implement the divide and conquer approach in C++. We will go through the steps of breaking down a problem into subproblems, solving the subproblems, and combining the solutions to obtain the final solution. We will also look at some examples of how to apply this technique to sorting and searching algorithms.

What is Divide and Conquer?

Divide and conquer is an algorithmic technique used to break down a problem into smaller, easier to solve subproblems. The idea is to divide the problem into smaller parts, solve each part separately, and then combine the solutions to obtain the final solution. This technique is useful when the problem is too complex to solve in one step. By breaking it down into smaller parts, the problem becomes easier to solve.

Divide and Conquer in C++

When implementing divide and conquer in C++, the first step is to identify the problem. This means understanding what the problem is and what it requires. Once the problem is understood, it can be divided into smaller, easier to solve subproblems. The subproblems can then be solved one at a time, and the solutions combined to obtain the final solution.

Example 1: Quicksort

Let us look at an example of how to use the divide and conquer approach to solve the quicksort problem. Quicksort is an algorithm used to sort an array of numbers in ascending order. The idea is to select a pivot element, and then divide the array into two parts, one containing elements smaller than the pivot, and the other containing elements larger than the pivot. These two parts are then sorted separately using quicksort, and the two sorted parts are combined to obtain the final sorted array.

// Quicksort algorithm in C++
int partition(int arr[], int low, int high) 
{ 
    int pivot = arr[high]; 
    int i = (low - 1); 
  
    for (int j = low; j <= high - 1; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++; 
            swap(arr[i], arr[j]); 
        } 
    } 
    swap(arr[i + 1], arr[high]); 
    return (i + 1); 
} 

void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        int pi = partition(arr, low, high); 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 

Example 2: Binary Search

Now let us look at an example of how to use the divide and conquer approach to solve the binary search problem. Binary search is an algorithm used to find the position of an element in a sorted array. The idea is to divide the array into two parts, one containing elements smaller than the element to be searched, and the other containing elements larger than the element to be searched. The element to be searched is then compared to the middle element of the array. If it is smaller than the middle element, the search is continued in the left half of the array, and if it is larger than the middle element, the search is continued in the right half. This process is repeated until the element is found or the array is exhausted.

// Binary search algorithm in C++ 
int binarySearch(int arr[], int low, int high, int key) 
{ 
    if (high >= low) 
    { 
        int mid = low + (high - low) / 2; 
  
        if (arr[mid] == key) 
            return mid; 
  
        if (arr[mid] > key) 
            return binarySearch(arr, low, mid - 1, key); 
  
        return binarySearch(arr, mid + 1, high, key); 
    } 
  
    return -1; 
} 

Conclusion

In this article, we have discussed how to implement the divide and conquer algorithm in C++. We have looked at two examples of how to apply this technique to sorting and searching algorithms. We have seen how the technique can be used to break down a complex problem into smaller parts, solve each part separately, and then combine the solutions to obtain the final solution.

Exercises

#include <iostream> 
using namespace std; 
  
int findMax(int arr[], int low, int high) 
{ 
    int mid; 
  
    if (low == high) 
        return arr[low]; 
  
    if (low < high) 
    { 
        mid = (low + high) / 2; 
  
        int leftMax = findMax(arr, low, mid); 
        int rightMax = findMax(arr, mid + 1, high); 
  
        if (leftMax > rightMax) 
            return leftMax; 
        else
            return rightMax; 
    } 
} 
  
int main() 
{ 
    int arr[] = {3, 5, 2, 1, 4}; 
  
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout << "The maximum element is " << findMax(arr, 0, n - 1); 
  
    return 0; 
}

#include <iostream> 
using namespace std; 
  
int findMin(int arr[], int low, int high) 
{ 
    int mid; 
  
    if (low == high) 
        return arr[low]; 
  
    if (low < high) 
    { 
        mid = (low + high) / 2; 
  
        int leftMin = findMin(arr, low, mid); 
        int rightMin = findMin(arr, mid + 1, high); 
  
        if (leftMin < rightMin) 
            return leftMin; 
        else
            return rightMin; 
    } 
} 
  
int main() 
{ 
    int arr[] = {3, 5, 2, 1, 4}; 
  
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout << "The minimum element is " << findMin(arr, 0, n - 1); 
  
    return 0; 
}

#include <iostream> 
using namespace std; 
  
int findSum(int arr[], int low, int high) 
{ 
    int mid; 
  
    if (low == high) 
        return arr[low]; 
  
    if (low < high) 
    { 
        mid = (low + high) / 2; 
  
        int leftSum = findSum(arr, low, mid); 
        int rightSum = findSum(arr, mid + 1, high); 
  
        return leftSum + rightSum; 
    } 
} 
  
int main() 
{ 
    int arr[] = {3, 5, 2, 1, 4}; 
  
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout << "The sum of the elements is " << findSum(arr, 0, n - 1); 
  
    return 0; 
}

#include <iostream> 
using namespace std; 
  
float findAverage(int arr[], int low, int high) 
{ 
    int mid; 
  
    if (low == high) 
        return arr[low]; 
  
    if (low < high) 
    { 
        mid = (low + high) / 2; 
  
        float leftAverage = findAverage(arr, low, mid); 
        float rightAverage = findAverage(arr, mid + 1, high); 
  
        return (leftAverage + rightAverage) / 2; 
    } 
} 
  
int main() 
{ 
    int arr[] = {3, 5, 2, 1, 4}; 
  
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout << "The average of the elements is " << findAverage(arr, 0, n - 1); 
  
    return 0; 
}

#include <iostream> 
using namespace std; 
  
int merge(int arr[], int temp[], int left, int mid, int right) 
{ 
    int i, j, k; 
    int inv_count = 0; 
  
    i = left; 
    j = mid;  
    k = left; 
    while ((i <= mid - 1) && (j <= right)) 
    { 
        if (arr[i] <= arr[j]) 
        { 
            temp[k++] = arr[i++]; 
        } 
        else
        { 
            temp[k++] = arr[j++]; 
            inv_count += (mid - i); 
        } 
    } 
  
    while (i <= mid - 1) 
        temp[k++] = arr[i++]; 
  
    while (j <= right) 
        temp[k++] = arr[j++]; 
  
    for (i=left; i <= right; i++) 
        arr[i] = temp[i]; 
  
    return inv_count; 
} 
  
int _mergeSort(int arr[], int temp[], int left, int right) 
{ 
    int mid, inv_count = 0; 
    if (right > left) 
    { 
        mid = (right + left)/2; 
  
        inv_count  = _mergeSort(arr, temp, left, mid); 
        inv_count += _mergeSort(arr, temp, mid+1, right); 
  
        inv_count += merge(arr, temp, left, mid+1, right); 
    } 
  
    return inv_count; 
} 
  
int mergeSort(int arr[], int array_size) 
{ 
    int temp[array_size]; 
    return _mergeSort(arr, temp, 0, array_size - 1); 
} 
  
int main() 
{ 
    int arr[] = {1, 20, 6, 4, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    int ans = mergeSort(arr, n); 
  
    cout << "Number of inversions are " << ans; 
    return 0; 
}