分而治之思想来源于拿破仑的一次杰出策略
拿破仑在应对一次大型进攻时没有采取硬碰硬的策略，而是将敌军分割（Divide）为两部分。然后集中优势兵力各个击破（Conquer）。
在较大问题十分棘手的时候，如果将其切分成若干容易得出结果的较小实例再进行合并，往往能起到令人意向不到的效果。如果划分后得到的部分还是较为难以计算，就将其继续切分直至得到易于计算的实例。因此，分而治之思想也被称为自顶向下（Top-Down）方法。这部分书上主要介绍了几种典型算法。
1. 二分查找 Binary Search
1.1 算法介绍
二分查找是在一个有序数组中查找一个数x并返回其位置。该算法首先将x与数组中间项进行比较，如果恰巧相等，那么便返回中间项的位置；如果不等，便将数组中间项同x进行比较。由于该数组是有序的，确定了数组中间项同x的关系，我们就可以确定x在数组的前半部分还是后半部分。一个较大的数组也因此被分割成两个部分，再对分割后的小部分进行查找，最终便可以完成在整个数组的查找。
1.2 算法流程
index location(index low,index high){
index mid;
if(low>high)return 0;
else{
mid=floor((low+high)/2);
if(x==S[mid])
return mid;
else if(x<S[mid])
return location(low,mid-1);
else
return location(mid+1,high);
}
}
1.3 算法实例
#include<iostream>
using namespace std;
#define CASE {1,3,4,5,6,7,8,9,12,41,67,89,100,235,567,890,2341,2346,5648}
int binarySearch(int low,int high,const int* input,const int number){
int mid=(low+high)/2;
if(low > high)return 0; //If the lower index is bigger than the higher index, the search ends with number not found;
else{
if(number==input[mid]){ //If the number equals to the mid-index-number in the list
return mid;
}
else if (number < input[mid])
{
binarySearch(low,high-1,input,number); //Get into Recursion with higher index-1
}
else
{
binarySearch(low+1,high,input,number);//Get into Recursion with lower index+1
}
}
}
int main(void){
int input[19]=CASE;
int index=binarySearch(0,18,input,89);
cout<<"The index is "<<index+1<<" , while the number is "<<input[index]<<endl;
return 0;
}
1.4 Algorithm Analysis
The most time-costing operation in this case is comparing operation, we thus treat that as the base operator in the algorithm.
We first set n is a power of 2. We notice that there will be two comparisons for target x with S[mid-0.5],S[mid+0.5]. But for an efficient assembler language implementation, we can assume that there is only one comparison.
For worst-case time complexity, we may set x is the biggest number in the array. By then each recursive calls half as big as the current array. Thus
W(n)=W(\frac{n}{2})+1
Attention that the 1 following is the first call of the entire array. If n=1(2^0), There is only one comparison. This recurrence is solved as follows:
W(n)=\lg n+1
If n is not a power of 2, we also get
W(n)=\lfloor \lg n\rfloor+1\in \Theta(\lg n)
2. Merge Sort
2.1 Background
In this algorithm, we apply mainly Two-way merging: Combining two sorted array in one bigger sorted array. First we divide the input array into two smaller array. Then sort the subarrays by recursion until it become small enough. Finally we combine the subarrays to a ordered array.
2.2 Algorithm
#include<iostream>
#include<math.h>
using namespace std;
int input[14]={1,3,5,7,34,2,67,4,165,68,92,24,58,92};
void merge(int* total,int upper_index,const int* upper,int bottom_index,const int* bottom){
//Merge the divided list
int i=0,j=0,k=0; //Set the start index
while(j<upper_index&&i<bottom_index){ //J concerns the upper part;I concerns the lower part
if(bottom[i]<upper[j]){ //Choose the bigger element
total[k]=bottom[i];
i++;
}
else{
total[k]=upper[j];
j++;
}
k++;
}
if(i==bottom_index){ //Pick the unselected element;
for (int m = j; m < upper_index; m++){
total[m+bottom_index]=upper[m];
}
}else{
for (int n = i; i < bottom_index; i++)
{
total[n+upper_index]=bottom[n];
}
}
}
void mergeSort(int index,int* inputlist){
if(index>1){
int lowerpart=floor(index/2);
int higherpart=index-lowerpart;
int upper[higherpart],bottom[lowerpart];
for(int i=0;i<lowerpart;i++)
{
bottom[i]=inputlist[i];
}
for (int j = 0; j < higherpart; j++)
{
upper[j]=inputlist[j+lowerpart];
}
mergeSort(lowerpart,bottom);//Divide and conquer
mergeSort(higherpart,upper);
merge(inputlist,higherpart,upper,lowerpart,bottom);
}
}
int main(void){
mergeSort(14,input);
return 0;
}
2.3 Algorithm analysis
In the case of algorithms that sort by comparing keys, the comparison instruction and assignment instructions can each be considered as the basic operation. We only take the comparing instruction into considerations here.
First we consider the worst-case time cost of the merging operation: the loop just exits when i = h+1 and j = m. Under such circumstance, all keys in array V(i) have been compared and there in also one key uncompared in U(i). Thus we have
W(h,m)=h+m-1
Return to the analysis of merge-sort, by recursion we get such expression:
W(n)=W(h)+W(m)+(h+m-1)
W(h) and W(m) are the recursion part of the expression which means the divided part from the original array, (h+m-1) represents the time costs combining these two arrays.
When n is a power of 2, we get
W(n)=W(\frac{n}{2})+W(\frac{n}{2})+n-1\\
= 2W(\frac{n}{2})+n-1
Solve such equation, we get
W(n)=n\lg n-(n-1)\in\Theta(n\lg n)
3. Quick Sort
3.1 Background
Quick sort is a algorithm similar to Mergesort that sorting is accomplished by dividing the array into two parts and sort each part recursively. However, mergesort partition the array by half while the quick divide the array by a pivot value: placing all the values smaller that the pivot in the left while the others in the right.
3.2 Algorithm
#include<iostream>
using namespace std;
int input[14]={1,3,5,7,34,2,67,4,165,68,92,24,58,92};
void partition(int low,int high,int& partition_point,int* input)
{
int j=low;
int partition_item=input[partition_point];
for(int i = low+1 ; i< high; i++){
if(input[i]<partition_item){
j++; //Move to the next number
int cache=input[j];
input[j]=input[i];
input[i]=cache; //Swap S[j] and S[i]
}
}
partition_point=j;//Cuz all number swapped is lower that S[low]
int cacheb=input[j];
input[j]=input[low];
input[low]=cacheb;//Swap S[pivot] and S[low]
for(int i=0;i<13;i++){
cout<<input[i]<<" ";
}cout<<endl;
}
void quickSort(int low,int high,int* input){
int partition_point;
if(low<high){
partition(low,high,partition_point,input);
quickSort(low,partition_point-1,input);
quickSort(partition_point+1,high,input);
}
}
int main(void){
quickSort(0,13,input);
}
3.3 Algorithm analysis
Quick-sort is a very important algorithm so we will calculate both the worst-case time complexity and the average time complexity.
For the worst case, if one of the sublists returned by the partitioning routine is of size n − 1. This happens when the pivot value is the biggest or the smallest value within the array. Then for the recurrence expression:
T(n)=T(n-1)+T(0)+(n-1)_{partitioning cost}
The solution can be
T(n)=\frac{n(n-1)}{2}
Thus when the array is already ordered, this algorithm reaches the worst case
W(n)=\frac{n(n-1)}{2}\in \Theta(n^2)
For the average case, we set that the pivot value divide the array into two parts in balance, which means that
T(n)=T(\frac{n}{2})+T(\frac{n}{2})+n-1\\
= 2T(\frac{n}{2})+n-1
Applying the Master theo of dnc recurrences , we got
T(n)\in \Theta(n\lg n)
4. Threshold in Divide and Conquer Algorithms
This part will be finished soonly