###### tags: `演算法`
# *2022/04/14 演算法作業 HW02*
## 題目:

## 解答:
最差情況：W(n/2)+1，所以lg 7億+1= 29…..+1次 ⼤約30～31次

## 題目:

## 解答:

void Algorithm_Create(int *list,int key){
    int Size_Of_List = sizeof(list);
    int *LeftSub_List = (int*)malloc((Size_Of_List/3)*sizeof(int));
    int *RightSub_List = (int*)malloc((Size_Of_List/3)*sizeof(int));
    int *MiddleSub_List = (int*)malloc((Size_Of_List-(sizeof(LeftSub_List))-(sizeof(RightSub_List)))*sizeof(int));
    int index=0;
    //Set the Left of SubMatrix
    for (int i=0;i<sizeof(LeftSub_List);i++){
        LeftSub_List[i]=list[i];
    }
    index=sizeof(LeftSub_List);
    //Set the Middle of Matrix
    for (int i=index,j=0;j<sizeof(MiddleSub_List) && i<(index+sizeof(MiddleSub_List));i++,j++){
        MiddleSub_List[j]=list[i];
    }
    index = index+sizeof(MiddleSub_List);
    //Set the Right of Matrix
    for (int i=index,j=0;j<sizeof(RightSub_List) && i<sizeof(list);i++,j++){
        RightSub_List[j]=list[i];
    }
    //Check that which Sublist might has the key
    if (key<LeftSub_List[sizeof(LeftSub_List)-1]){
        Algorithm_Create(LeftSub_List,key);//In the Left Sub Matrix
    }
    else if (key<MiddleSub_List[sizeof(MiddleSub_List)-1]){
        Algorithm_Create(MiddleSub_List,key);
    }
    else if (key<RightSub_List[sizeof(RightSub_List)-1]){
        Algorithm_Create(RightSub_List,key);
    }
    else if (index ==0){
        printf(“The %d is not in this list”,key);
    }
    else{
        printf(“Congratulation! You find the Key”);
    }
}

### 說明:
因為每次都把List切成三等份，所以最差最差:W(n/3)+1，不存在every-case，因為每⼀次不⼀定，但有WorstCase
W(n):W(n/3)+1，g(n)=（以3為底，n的對數值）所以屬於theta(logn)

## 題目:
## 解答:

## 題目:

void MergeSort_Revice(int n,keytype S[ ]){
    if (n>1){
        const int l=n/3,r=n/3,m=n-l-r;
        keytype U[1…..l], V[1….m], K[1….r];
        將S[1]到S[l]複製到U[1…..l];
        將S[l+1]到S[m]複製到V[1…..m];
        將S[m+1]到S[r]複製到U[1…..r];
        MerSort (l,U);
        MerSort (r,V);
        MerSort (m,K);
    }
    merge_Revice(l,r,m,U,V,K,S);
}
void merge_Revice(int l,int r, int m, const keytype U[ ],const keytype V[ ], const keytype K[ ], const keytype S[ ]){
    index i,j,k;
    //比較數值
    從3個SubList中找出最⼩的，取代原本S[ ]的第⼀個值，依序下去，直到三個SubList都讀取完成結束
}

## 說明:
因為每⼀次都把陣列切成3等份，所以W(n)=W(l)+W(r)+W(m)+(l+r+m-1)，分別代表排列左邊List 中間List 右邊List 還有
最後合併的最差情況，所以最後的W(n)依舊屬於Theta(nlgn)

## 題目:
## 解答:

## 題目:

## 解答:

## 題目:
## 解答:
* (a) 最差情況：每次pivot的⼀邊都為NULL，例如要輸出遞增數列，可給定的數列為遞減，且每次pivot都選定第⼀個值
* EX：{10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }
* (b) 最佳情況：每次pivot的⼀邊只有⼀個值，這樣可以花最少的步驟排列
* EX：{2, 1, 4, 3, 6, 5, 8, 7, 10, 9}

## 題目:
## 解答:

## 題目:

## 解答:

## 題目:

## 解答: