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