Divide And Conquer Algorithms With Python

Divide and Conquer(D&C) is a concept for data structures and algorithms that repeatedly cuts the input in half until we achieve our goal. Divide and Conquer algorithms are not too far off from dynamic programming. Where they both recursively cut the input size in half, but the difference is if you need to calculate something and keeping track of that change, then using memoization in dynamic programming is preferred.

There are many Divide and Conquer Algorithms and we will check out when they should be used, and how they can be implemented.

QuickSort

The QuickSort like its name suggests, is a sorting algorithm. It chooses a pivot point in which the rest of the input array gets sorted around. This pivot can be the first, last, or middle most element in the array. The runtime can vary greatly depending on what you choose your pivot point as.

python example from GeeksForGeeks

def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 

    for j in range(low , high): 

        if   arr[j] < pivot: 

            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 

def quickSort(arr,low,high): 
    if low < high: 

        pi = partition(arr,low,high) 

        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high)

Binary Search

This searching algorithm is the first algorithm I think of when I see Divide and Conquer. This algorithm only works if the input array is already sorted. We take in an input array and a desired number we are searching for. Then we compare to the middle most element in the array. If our desired element is less than the middle most element, then we chop off the top half of the array and repeat the process. If our element was bigger than the middle most element, then we do the opposite by only looking at the larger elements of the array.

pseudo example

def binarySearch(arr, desiredNum):
     mid = arr.length/2

     if(desiredNum > arr[mid])
          look at first half of array
          reset mid within scope of array
          repeat search
     else
          look at bigger half of array
          reset mid within scope of array
          repeat search
return index of element

Merge Sort

Merge sort is a pretty cool sorting algorithm that splits the whole array into two until it is all split up, then slowly start sorting them together.

pseudo code from GeeksForGeeks

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)