Please enable JavaScript.
Coggle requires JavaScript to display documents.
Selection Sort, Decrease-and-Conquer, Insertion Sort, Bubble Sort,…
-
-
-
-
-
Divide-and-Conquer
-
Master Theorem If f(n) ∈ Θ(nˆd) where d ≥ 0 in general divide-and-conquer recurrence, then:
-
-
-
-
-
is a technique based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance
-
is a bottom-up variation that is usually implemented iteratively, starting with a solution to the smallest instance of the problem
suggests reducing a problema instance by the same constant factor on each iteration of the algorithm
-
- application of the decrease-by-one technique to sorting an array
- it is assumed that the smaller problem of sorting the array A[0..n-2] has already been solved to five us a sorted array of size n-1: A[0]≤....≤A[n-2]
-
-
1- A problem is divided into several subproblems of the same type, ideally of the same size
2- The subproblems are solved
3- If necessary, the solutions to the subproblems are combined to get a solution to the original problem
-
-
- application of the the divide-and-conquer technique to sorting an array
- it sorts a given array A[0..n-1] by dividing it into two halves, sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one
- Two pointers are initialized to point to the first elements of the arrays.
- The elements pointed are compared, and the smaller of them is added to a new array.
- It keeps going, just increasing the index of the arrays.
divide a list to be sorted in more than two parts, sort each exclusively, and then merge them together
-
-