Divide and Conquer Algorithms
Divide and conquer is a way to break complex problems into smaller problems that are easier to solve, and then combine the answers to solve the original problem. Divide and conquer is a powerful algorithm used to solve many important problems such as merge sort, quick sort, selection sort and performing matrix multiplication. There are also many problems that humans naturally use divide and conquer approaches to solve, such as sorting a stack of cards or looking for a phone number in a phone book.
Divide and conquer can be done in three steps, divide into subproblems, conquer by solving the subproblems, and combine the answers to solve the original problem. Divide and conquer has usually a recursive step, where subproblems are solved, and a base case, which is the point where the problem can’t be broken down any further.
Example:
Sorting an array in ascending order using Merge Sort
Source: Geeks for Geeks
Source: Geeks for geeks
Merge sort:
Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.
Steps:
Divide the unsorted list into sublists, each containing 1 element.
Take close pairs of two lists and merge them to form a list of 2 elements. N will now convert into N/2 lists of size 2.
Repeat the process till a single sorted list of obtained.
Implementation of Merger Sort Algorithm in python:
QuickSort :
QuickSort is one of the most efficient sorting algorithms and is based on the splitting of an array into smaller ones. The name comes from the fact that, quick sort is capable of sorting a list of data elements significantly faster than any of the common sorting algorithms. And like Merge sort, Quick sort also falls into the category of divide and conquer approach of problem-solving methodology.
Steps:
Choose the highest index value has pivot
Take two variables to point left and right of the list excluding pivot
Left points to the low index
Right points to the high
While value at left is less than pivot move right
While value at right is greater than pivot move left
If both step 5 and step 6 does not match swap left and right
If left ≥ right, the point where they met is new pivot
Implementation of Quick Sort Algorithm in python:
Selection Sort:
The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.
Source Hackerearth.com
Implementation of Selection sort Algorithm in python:
Measured of Running Time in Differences Divide and Conquer Algorithms
Running time is faster for Quick Sort.
Divide and conquer algorithms are one of the fastest and perhaps easiest ways to increase the speed of an algorithm and are very useful in everyday programming.
Source: mobisoftinfotech.com
