In a Divide and Conquer Paradigm we divide the bigger problem into smaller sub problems and call the function recursively to solve the sub problems. Divide and Conquer method is more appropriate for those problems that have polynomial time solutions. Some of the Divide and Conquer Algorithms are Insertion sort, bubble sort, etc. Read this to know more about this algorithms HERE
Divide and Conquer Paradigm. 3 – Steps
Divide. Divide the bigger Problem into smaller sub problems.
Conquer. Solve the sub problems recursively, if the sub problem is very small then solve it in straight-forward manner.
Combine. combine all the solutions into the solutions of original problem.
Problem: Given an array of size n, sort them in ascending order.
- Divide the n elements into the n/2 subarrays.
- Sort the two subarrays in recursively.
- Merge the two subarrays into the sorted array
Algorithm of Merge Sort
Sort: If len(array) > 1: s = len(array)/2 A = array - 0 to A B = array - A to len(array) Sort(A) Sort(B) c = Merge(A,B) return c
Merge: len_c = len(A) + len(B) i = 0 j = 0 for k = 0 to Len_c if A[i] <= B[j] C[k] = A[i] i = i + 1 else: C[k] = B[j] j = j + 1 return C
Time complexity of the algorithm is nlog2n where the base is 2. The time complexity of Merge function is O(n).
log2n is the number of levels.
Which Sorting Algorithm is of Divide and Conquer Type?
Def. Any Algorithm which can Divide a bigger problem into smaller problems and give a combined solution is of Divide and Conquer type. Usually these have Time complexity in logn. In order to identify the Sorting algorithm as Divide and Conquer type you can look at is time complexity.
Algorithms related posts visit HERE
Data Structures related posts visit HERE
Databases related posts Visit HERE
Python-related posts Visit HERE
C++ related posts Visit HERE
Data Science related posts visit HERE