Comment on page
Divide and Conquer
- Divide the problem into multiple subproblems in smaller size.
- Conquer the subproblems recursively; set a straight forward way for base case.
- Combine the solutions to the subproblems into the solution for the original problem.
- recurrence relation:
- the number of subproblems in the recursion
- the factor by which the subproblem size is reduced in each recursive call
- andis asymptotically positive (positive for sufficiently large)
- base case:is a constant whenis a constant
- comparewithand this will lead to three regimes (>, =, <)
- in recursion tree, compare root with leaves and see which part dominates
- more reference: CLRS book page 94
#include <iostream>
#include <vector>
int merge(std::vector<int>& A, int start, int end, int middle, std::vector<int>& B){
// combine
int i = start;
int j = middle;
for (int k = start; k<= end; ++k){
if (i < middle && (j > end || A[i] <= A[j]))
B[k] = A[i++];
else
B[k] = A[j++];
}
for (int k = start; k<= end; ++k){
A[k] = B[k];
}
}
int mergeSort(std::vector<int>& A, int start, int end, std::vector<int>& B){
// divide and conquer
if (end == start)
return 0;
int middle = (start + end + 1) / 2;
mergeSort(A, start, middle - 1, B);
mergeSort(A, middle, end, B);
merge(A, start, end, middle, B);
}
int main(){
int n;
std::cin >> n;
std::vector<int> score(n);
std::vector<int> temp(n);
for (int k = 0; k < n; ++k)
std::cin >> score[k];
mergeSort(score, 0, n-1, temp);
std::cout << n << std::endl;
for (int k = 0; k < n; ++k)
std::cout << score[k] << std::endl;
return 0;
}
Last modified 2yr ago