Divide and Conquer

The divide and conquer strategy is a powerful problem-solving technique used in various domains of computer science. It involves breaking down a complex problem into smaller, more manageable subproblems, solving them recursively, and then combining the solutions to solve the original problem.

This strategy is based on the principle of self-similarity and can be applied to problems that exhibit overlapping subproblems and optimal substructure.

Steps of the Divide and Conquer Strategy

The divide and conquer strategy can be summarized in the following steps:

1. Divide: Break down the problem into smaller, more manageable subproblems.

2. Conquer: Solve the subproblems recursively. If the subproblems are small enough, solve them directly.

3. Combine: Combine the solutions of the subproblems to obtain the final solution to the original problem.

Example: Merge Sort

Merge sort is a classic example that demonstrates the divide and conquer strategy. It is an efficient sorting algorithm that divides the unsorted array into two halves, recursively sorts each half, and then merges the sorted halves to obtain the final sorted array.

Here's an example of merge sort implemented in C++:

1#include <iostream>
2using namespace std;
3
4void merge(int arr[], int low, int mid, int high)
5{
6    // Merge logic
7}
8
9void mergeSort(int arr[], int low, int high)
10{
11    // Merge sort logic
12}
13
14int main()
15{
16    // Test array
17    int arr[] = {12, 11, 13, 5, 6, 7};
18    int n = sizeof(arr) / sizeof(arr[0]);
19
20    // Original array
21    cout << "Original array: ";
22    for (int i = 0; i < n; i++)
23        cout << arr[i] << " ";
24    cout << endl;
25
26    // Call merge sort
27    mergeSort(arr, 0, n - 1);
28
29    // Sorted array
30    cout << "Sorted array: ";
31    for (int i = 0; i < n; i++)
32        cout << arr[i] << " ";
33    cout << endl;
34
35    return 0;
36}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

void merge(int arr[], int low, int mid, int high)

{

    int n1 = mid - low + 1;

    int n2 = high - mid;

​

    int left[n1], right[n2];

​

    for (int i = 0; i < n1; i++)

        left[i] = arr[low + i];

    for (int j = 0; j < n2; j++)

        right[j] = arr[mid + 1 + j];

​

    int i = 0, j = 0, k = low;

​

    while (i < n1 && j < n2) {

        if (left[i] <= right[j]) {

            arr[k] = left[i];

            i++;

        }

        else {

            arr[k] = right[j];

            j++;

        }

        k++;

    }

​