Divide and Conquer

Divide and conquer 即系將一個大問題切成一D小問題（小問題可能系大問題既 General case 或者 Special case，亦可能同大問題完全無關），通過解決小問題之後組合解決大問題。

由於可以將問題抽象化，變為 General case 同 Special case，一般 Divide and conquer 都比較容易思考同 Prove。至於 Implementation 則可能用 Recursion 或 Loop（一般其實系將 Recursion 變為 Loop）。

1. Finding maximum in an array

可能你一眼望埋個問題已經有答案：用 for loop through the array, compare the current maximum and the array item, and store the maximum value.

問題系，你點知呢個做法是否正確呢？換句話來講，即係你點 Prove 呢？ 其實用 For loop 已經唔系最直接既做法，最直接既做法其實系 Recursion，但你可能由頭到尾都冇諗過。以下系唔同既 Case。

1. Special: 如果個 Array 得一個 Item，maximum 就肯定系果個 Item。（好似好廢，但其實系重點）
2. General Case: Given 2 個 Array 同佢地最大既 Item，佢哋 Combine 之後既 Array 既 Maximum 就係兩個最大 Item 裡面最大果個。
3. 所以如果有一個 Array，只需要檢查是否 Special case，如果系就直接 return 裡面個 item；唔系既話就切成兩個較小既 Array，搵出佢哋既 Maximum，最後 return 佢哋之間最大既。

所以其實系點做 Recursion 既呢？以下系條pseudo-code

 
x
1
function max(a, b):
2
    //比較兩個數，return 最大既
3
    if a >= b:
4
        return a
5
    return b
6
function array_max(array, start, end):
7
    if start = end:
8
        //Special case, only 1 item
9
        return array[start]
10
    //如果系 General case，就分為兩個 array 處理
11
    //其實點切都得，但為左可以方便地轉為 Loop，直接切為第一個 item 同 array 之後既部分
12
    return max(array_max(array, start, start), array_max(array, start+1, end))

至於點變為 Loop 呢？其實好簡單，array_max(array, start, start) 其實同 array[start]冇分別，而之後 Recursion 到 array_max(array, start+1, end) 就可以視作 counter + 1 處理。

 
xxxxxxxxxx
1
10
9
10
1
function max(a, b):
2
    //比較兩個數，return 最大既
3
    if a >= b:
4
        return a
5
    return b
6
function array_max(array, start, end):
7
    maximum = array[start] //initialize maximum to be one of the array's element
8
    //由於 start 已經被處理，所以可以 skip 到 start + 1
9
    for i from start + 1 to end:
10
        //如果你鐘意，甚至可以寫 if array[i] > maximum: maximum = array[i]
11
        maximum = max(maximum, array[i])
12
    return maximum

2. Binary search

Binary search 系針對 sorted list 既 search，原理其實都好簡單，都係 recursion。

1. 假設個 list 系 ascending 既。（如果系 descending 就講前後調轉）

2. 如果個 list 根本冇野，咁就肯定唔會搵到啦，收工。

3. 如果個數 = 個 list 中間個 element => 搵到收工。

   1. 如果要搵既野大於中間個 element，就代表要搵既 element 只可能系個 list 既後半部分（因為ascending）或者根本唔存在。就對個 list 既后半部分做 Binary search (recursion)
   2. 如果小於，就代表要搵既野只可能系個 list 既前半部分或者根本唔存在。就對個 list 既前半部分做 Binary search (recursion)

 
x
10
1
//ascending
2
function bsearch(item, array, start, end):
3
    //睇完之後部分再睇呢部分，因為同後面 start 同 end 既處理有關
4
    if start > end:
5
        //搵唔到
6
        return -1
7
​
8
    //注意，假設start同end為 4 同 5，middle會系 4
9
    //因為 interger division 系 round down 既
10
    middle = (start + end)/2     
11
    if item > array[middle]:
12
        //bsearch 后半部分
13
        //後半部分既 start 就係 middle + 1，因為 middle 已經 check 左
14
        //  假設個 list 得一個 item，即 start = end
15
        //  => middle = end => middle + 1 > end
16
        //  會造成個 function 開頭搵唔到既 case
17
        return bsearch(item, array, middle+1, end)
18
    else if item < array[middle]:
19
        //bsearch 前半部分
20
        //end 系 middle - 1，因為 middle 已經 check 左
21
        //  假設個 list 有1-2個 item，即 start = end / end+1
22
        //  => middle = start => start < middle - 1
23
        //  會造成個 function 開頭搵唔到既 case
24
        return bsearch(item, array, start, middle-1)
25
    else:
26
        //item = array[middle]
27
        return middle

要改為 Loop 甚至更簡單，因為呢個其實系 Tail Recursive，簡單來講即係 return value = return value of the next recursive call.

 
xxxxxxxxxx
1
10
1
//ascending
2
function bsearch(item, array, start, end):
3
    while start < end:
4
        middle = (start + end)/2
5
        if item > array[middle]:
6
            //本來系 Recursion，但結果其實同下個 Loop 既結果一樣
7
            start = middle + 1
8
        else if item < array[middle]:
9
            //同上
10
            end = middle - 1
11
        else:
12
            //注意 return 會 break loop，即令 loop 提早結束
13
            return middle
14
    return -1

注意，一切二分(Bisection)既野（只論二分既部分），如 Binary search，既 Time complexity 系 $O(log_2n)$

3. Merge sort

1. Special case: 如果個 List 得一個 Item，佢一定系 Sort 好既。

2. General case: Given 2 個 sorted list，你可以好快將佢哋 combine 做一個 sorted list

   1. 每次將兩個 list 中最大/最小既 item 放入目標 list裡面。方法系比較兩個 list 既第一個 item，要最小/大既。（兩個list 裡面最小/大既 item 必定系第一個，否則就唔系 sorted list）

      呢個方法既 Time complexity 系 $O(n)$，因為一共要放 n 次（假設兩個 list 既 item 總數為 n）

為左夠快，merge sort 系分落去既步驟用左二分既方法：即把個 list 分為前後兩半，Recursion 直至得 1 個 element。所以佢既 time complexity 系 $O(n log_2n)$ （層數 = $log_2n$，每層需要做既 merge 既 item 總數必定為 n）

 
x
10
1
//假設一切都系ascending
2
//為了方便，我假設一切 array 都會被複製，但事實並不是如此，請注意
3
//並且我假設 array 開始 index = 0, last element index = n-1
4
function merge(a, b):
5
    i = 0 //a counter
6
    j = 0 //b counter
7
    result = array[a.length + b.length] //temp array, length = sum of 2 array
8
    while i <> a.length or j <> b.length: //即其中一個未完成
9
        //如果 b 已經空了 => 只能處理 a
10
        //如果 b 不為空，而且 a[i] < b[j] => 處理 a
11
        //  注意，我這裡偷懶用 or 處理，因為如果 b 已經空了，
12
        //  or的條件就已經滿足，不會檢查後方條件，也不會出錯(b 的 Index out of range)
13
        if j = b.length or a[i] < b[j]:
14
            //append the item in a
15
            result += a[i]
16
            i = i+1
17
        else:
18
            //只能做b
19
            result += b[j]
20
            j = j+1
21
    return result
22
​
23
function sort(items):
24
    if items.length = 1:
25
        //special case: 1 item array
26
        return items
27
    //將 Array 分為一半涉及一些 language specific 既 function，所以就直接寫前半、後半算數
28
    return merge(sort(items.前半), sort(items.後半))

4. Quicksort

其實已經 Out syl，但因為個 Algorithm 好正所以順便講埋。

Quicksort 理論上速度比 merge sort 慢，但因為佢可以做到 in-place sorting （merge sort merge 既時候一定要個 temporary array，所以唔可以 in-place），所以實際效率比 merge sort 好。

Quicksort 重點系搵 Pivot element。Pivot element 決定 Quicksort 會點將個 Array 劃分為兩部分：一部分比 Pivot element 小，一部分比 Pivot element 大。選擇得好既話(median)，個 Array 就會被分為兩部分，即二分，效率最高，但我地系 sort 之前其實系唔會知道個 Array 既 median 系幾多，所以要睇運氣。

Quicksort Pivot 位置選擇可以造成 Worse case，為左避免 sorted array可能造成 worse case 既情況，所以實際使用時一般會用 random pivot，但為左方便起見，例子唔會用 random pivot，而系用 largest index。

下方解釋以 ascending 為例。

1. 我地將 Array 分為兩部分：前半部分比 Pivot element 小，後半部分比 Pivot element 大或一樣。（注意，一般情況下這並非 sorting，而呢個部分就係精粹，建議唔理解既話 Dry run 一下）

   1. 想象個 Array 分為三部分：< Pivot, >= Pivot, unknown。（1、2部分一開始長度為 0，unknown部分為全部）你需要 manage 幾個 variable:

      1. lower: Array 第一個 element 既 index
      2. higher: Array最後一個 element 既 index，亦系 pivot index
      3. less = lower - 1，即 < Pivot 部分最後一個 element 既 index
      4. i = lower，即 unknown 部分第一個 element 既 index

      然後直接上 code 算

       
      xxxxxxxxxx
      25
      1
      function partition(array, lower, higher):
      2
          less = lower-1
      3
          //唔 Loop 到 higher 系因為 higher 就係個 Pivot，冇必要比較
      4
          for i from lower to higher - 1:
      5
              //每次 Loop 就代表 unknown 部分長度減少
      6
              
      7
              //小於 pivot
      8
              if array[i] < array[higher]:
      9
                  //移動到 < Pivot既部分，但由於 < Pivot 既部分被 >= Pivot 既部分 bound 住
      10
                  //故此我地需要同時移動 >= Pivot 部分，但我地其實唔需要理會 >= Pivot 部分既順序
      11
                  //所以可以直接將 >= Pivot部分第一個同 array[i] swap
      12
                  //>= Pivot部分就等同移后左，而由於 <Pivot 同 >=Pivot部分系相連既
      13
                  //<Pivot既部分就等同長左
      14
                  temp = array[i]
      15
                  //less+1就係 >= Pivot 部分第一個 element既位置
      16
                  array[i] = array[less + 1]
      17
                  array[less+1] = temp
      18
                  less = less + 1
      19
              //如果 array[i] >= array[higher] 就唔需要處理
      20
              //因為 i 增加就代表 >=Pivot 部分最後既 index 增加，自動撥入 >=Pivot 部分
      21
          //最後把 pivot 放到兩部分之間
      22
          //確保 pivot 前必定比 pivot 小，pivot 后不會比 pivot 小
      23
          temp = array[higher]
      24
          array[higher] = array[less + 1]
      25
          array[less + 1] = temp
      26
          //最後 return pivot index
      27
          return less + 1
      

2. 之後只需要對兩部分做 Recursion，總會做到得返兩個 element，而兩個 element 做完 partition 就係 sorted。

 
xxxxxxxxxx
7
1
function quicksort(array, lower, higher):
2
    //得返一個 element 既時候就唔洗做
3
    if lower < higher:
4
        p = partition(array, lower, higher)
5
        //pivot 位置不需要繼續處理，因為前方的肯定比它小，後方的也不會比它小
6
        quicksort(array, lower, p-1)
7
        quicksort(array, p+1, lower)