Algorithm Divide And Conquer Strategy Complete Guide

Let's create complete examples with step-by-step explanations for beginners using two of these well-known algorithms: Merge Sort and Quick Sort.

Example 1: Merge Sort

Merge Sort is an example of the Divide and Conquer strategy. It works by dividing the array into halves, recursively sorting each half, and then merging the sorted halves.

Code Implementation:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle of the array
        left_half = arr[:mid]  # Divide the array elements into two halves
        right_half = arr[mid:]

        merge_sort(left_half)  # Recursively sort the first half
        merge_sort(right_half)  # Recursively sort the second half

        i = j = k = 0

        # Copy data to temp arrays left_half[] and right_half[]
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr

# Driver code to test above
arr = [38, 27, 43, 3, 9, 82, 10]
print("Given array is:", arr)
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr)

Step-by-Step Explanation:

1. Divide:

   • Start with the given array [38, 27, 43, 3, 9, 82, 10].
   • Compute the midpoint: mid = 7 // 2 = 3.
   • Divide the array into two halves:
     • Left Half: [38, 27, 43, 3]
     • Right Half: [9, 82, 10]

2. Recursively Sort Each Half:

   • Sort the Left Half: [38, 27, 43, 3].

     • Midpoint: mid = 4 // 2 = 2.
     • Further divide into two halves:
       • left_half = [38, 27]
       • right_half = [43, 3]
     • Sort [38, 27]:
       • Midpoint: mid = 2 // 2 = 1.
       • Further divide into two halves:
         • left_half = [38]
         • right_half = [27]
       • Base case reached (single element arrays are already sorted).
       • Merge back into a sorted array: [27, 38].
     • Sort [43, 3]:
       • Midpoint: mid = 2 // 2 = 1.
       • Further divide into two halves:
         • left_half = [43]
         • right_half = [3]
       • Base case reached.
       • Merge back into a sorted array: [3, 43].
     • Now merge the two sorted halves [27, 38] and [3, 43] into a single sorted array: [3, 27, 38, 43].

   • Sort the Right Half: [9, 82, 10].

     • Midpoint: mid = 3 // 2 = 1
     • Further divide into two halves:
       • left_half = [9]
       • right_half = [82, 10]
       • Sort [9]: Base case reached.
       • Sort [82, 10]:
         • Midpoint: mid = 2 // 2 = 1
         • Further divide into two halves:
           • left_half = [82]
           • right_half = [10]
           • Base cases reached.
         • Merge back into a sorted array: [10, 82]
     • Finally, merge the sorted halves [9] and [10, 82] to get a sorted right half: [9, 10, 82].

3. Combine:

   • Merge the two sorted halves [3, 27, 38, 43] and [9, 10, 82] to obtain the final sorted array: [3, 9, 10, 27, 38, 43, 82].

Example 2: Quick Sort

Quick Sort is another example of the Divide and Conquer strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

Code Implementation:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]  # Choose the middle element as pivot
        left = [x for x in arr if x < pivot]  # Elements less than pivot
        middle = [x for x in arr if x == pivot]  # Elements equal to pivot
        right = [x for x in arr if x > pivot]  # Elements greater than pivot

        return quick_sort(left) + middle + quick_sort(right)

# Driver code to test above
arr = [38, 27, 43, 3, 9, 82, 10]
print("Given array is:", arr)
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)

Step-by-Step Explanation:

1. Divide:

   • Start with the given array [38, 27, 43, 3, 9, 82, 10].
   • Choose the pivot element. Here, we choose the middle element: pivot = 43.
   • Partition the array into three parts:
     • Elements less than the pivot (left): [38, 27, 3, 9, 10]
     • Elements equal to the pivot (middle): [43]
     • Elements greater than the pivot (right): [82]

2. Recursively Sort Each Sub-array:

   • Sort the left sub-array [38, 27, 3, 9, 10]:
     • Choose the pivot: pivot = 9. (middle index in remaining numbers)
     • Partition: left = [38, 27, 3], middle = [9], right = [10]
     • Sort the left sub-array [38, 27, 3]:
       • Choose the pivot: pivot = 27.
       • Partition: left = [3], middle = [27], right = [38]
       • left = [3] is already sorted.
       • Combine: [3, 27, 38] and [9] to get [3, 27, 38, 9].
       • Then sort [10]: already sorted.
       • Combine: [3, 27, 38, 9, 10].
   • right sub-array [82] is already sorted.

3. Combine:

   • Combine the sorted left sub-array [3, 9, 10, 27, 38], middle sub-array [43], and sorted right sub-array [82] to obtain the final sorted array: [3, 9, 10, 27, 38, 43, 82].

Summary

Both Merge Sort and Quick Sort employ the Divide and Conquer strategy efficiently:

• Merge Sort: Divides the array consistently in half until individual elements remain, sorts them trivially, and merges them back together.
• Quick Sort: Chooses a pivot, partitions the array into elements less than, equal to, and greater than the pivot, and recursively sorts the sub-arrays.