2017年9月24日 星期日

[演算法] 合併排序法(Merge Sort)

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理,但部分程式碼是消化後以自己較易理解的方式重新撰寫,因此和原課程內容有些出入。

問題描述

透過函式將陣列中的數值加以排序。

前置知識:Merge Sort

Merge Sort 和 Bubble Sort 一樣,都是一種用來排序的演算法。
Merge Sort 的演算法主要包含兩個部分:

1. 將陣列對半拆分

Merge Sort 的第一步是要將陣列兩兩對半拆分,直到拆到每個陣列只剩一個元素:
// 原本的陣列
[3, 20, 8, 5, 1, 12, 17, 2]
// 進行對半拆分
[3, 20, 8, 5], [1, 12, 17, 2]
// 再拆分
[3, 20], [8, 5], [1, 12], [17, 2]
// 再拆分
[3], [20], [8], [5], [1], [12], [17], [2]

2.將陣列排序後加以合併

我們把上面拆分好的陣列,兩兩一組開始進行排序,每次排序時都是取該陣列的第一個元素進行比較:
// 拆分好的陣列
[3], [20], [8], [5], [1], [12], [17], [2]

// [3] vs [20]; [8] vs [5]; [1] vs [12]; [17] vs [2]
// 兩兩比較排序後合併,每次比較都是取當時陣列中的第一個元素進行比較
[3, 20], [5, 8], [1, 12], [2, 17]

// 再一次兩兩比較後排序後合併,每次比較都是取當時陣列中的第一個元素進行比較
[3, 5, 8, 20], [1, 2, 12, 17]

// 再一次兩兩比較後排序後合併,每次比較都是取當時陣列中的第一個元素進行比較
[ 1, 2, 3, 5, 8, 12, 17, 20 ]
兩兩比較後排序的方式可以參考下圖,每次比較都是取各陣列的第一個元素來進行比較:
整個合併排序法如下圖所示:
圖片來源:合併排序 @ wikipedia
因此我們一共需要兩個函式,並且一樣會透過遞回函式的方式來處理:
function mergeSort (arr) {
  // 接受一組尚未排序的陣列當作參數,將它們對半切分  
}

function sortBeforeMerge (arr1, arr2) {
  /**
   * 代入兩個已經各自排序過的陣列
   * 每次都取這兩個陣列中當時的第一個元素進行比較
   * 把數值小的放前面,最後合併成一個陣列
   **/
}
Merge Sort 這個演算法我覺得稍微有一點點小小複雜,非常需要圖像化來幫助思考,但我們可以先看 code ,看完之後會更瞭解它實際上的運作方式。

演算法實做

1. 將陣列進行對半切分

首先要將傳進來的陣列進行對半切分,這裡可以透過 Array.prototype.slice 來進行:
function mergeSort (arr) {
  // 接受一組尚未排序的陣列當作參數,將它們對半切分
  let middleIndex = Math.floor(arr.length / 2)
  let firstHalf = arr.slice(0, middleIndex)
  let secondHalf = arr.slice(middleIndex)  
}

2. 將兩組各自已經排序過的陣列以 merge sort 的方式合併

首先透過 while 迴圈,當傳入的兩組 已經各自排序過的 的陣列 arr1arr2 都沒有空陣列的情況下,選出兩陣列中當時的第一個元速進行比較,把比較小的先放入 sortedArr 中:
function sortBeforeMerge (arr1, arr2) {
  let sortedArr = []
  
  // 當 arr1 或 arr2 都不是空陣列時
  while (arr1.length && arr2.length) {
    // 以兩陣列中第一個元素進行比較,較小的推入 sortedArr 中
    let minElement = (arr1[0] < arr2[0]) ? arr1.shift() : arr2.shift()
    sortedArr.push(minElement)
  }
}
Array.prototype.shift() 可以把移除陣列中的第一個元素,並把它存出來。
經過 while 迴圈後,我們會得到一組已經經過 merge sort 方式排序好的陣列;另外,while 迴圈終止的條件是只要 arr1 或 arr2 其中一組為空陣列時就會停止,因此這時候 arr1 或 arr2 其中有一組還不是空陣列,我們要把不為空陣列的陣列透過 Array.prototype.concat 連接到 sortedArr 後面。
由於我們傳進 sortBeforeMerge 這個函式的陣列是已經經過排序的,因此,可以確定透過 concat 連結好的陣列,其數值也會是由小到大的:
function sortBeforeMerge (arr1, arr2) {
  let sortedArr = []
  
  // 當 arr1 或 arr2 都不是空陣列時
  while (arr1.length && arr2.length) {
    // ...
  }
  
  /**
   * 會跳出上面 while 的迴圈,表示 arr1 或 arr2 其中至少有一個為空陣列
   * 因此,如果 arr1 不是空陣列,則把它 concat 到 sortedArr 內;
   * 如果是 arr2 中不是空陣列,則把它 concat 到 sortedArr 內。
  **/
  sortedArr = arr1.length ? sortedArr.concat(arr1) : sortedArr.concat(arr2)
  return sortedArr
}

3. 結合遞回函式

最後我們要把 mergeSort 這個函式結合遞回的概念,在使用遞回函式時,一定要記得設定終止條件:
function mergeSort (arr) {
  
  // 遞回函式終止條件:當陣列被拆到只剩一個元素時
  if (arr.length <= 1) {
    return arr
  }
  
  // 接受一組尚未排序的陣列當作參數,將它們對半切分
  // ...
  
  // 遞回函式
  return sortBeforeMerge(mergeSort(firstHalf), mergeSort(secondHalf))
}

完整程式碼

function mergeSort (arr) {
  
  // 遞回函式終止條件:當陣列被拆到只剩一個元素時
  if (arr.length <= 1) {
    return arr
  }
  
  // 接受一組尚未排序的陣列當作參數,將它們對半切分
  let middleIndex = Math.floor(arr.length / 2)
  let firstHalf = arr.slice(0, middleIndex)
  let secondHalf = arr.slice(middleIndex)
  
  // 遞回
  return sortBeforeMerge(mergeSort(firstHalf), mergeSort(secondHalf))
}

function sortBeforeMerge (arr1, arr2) {
  /**
   * 代入兩個已經"各自排序過"的陣列,
   * 將這兩個陣列利用 merge sort 的方式排序後,合併回傳成一個陣列
   **/
  let sortedArr = []
  
  // 當 arr1 或 arr2 都不是空陣列時
  while (arr1.length && arr2.length) {
    // 以兩陣列中第一個元素進行比較,較小的推入 sortedArr 中
    let minElement = (arr1[0] < arr2[0]) ? arr1.shift() : arr2.shift()
    sortedArr.push(minElement)
  }
  
  /**
   * 會跳出上面 while 的迴圈,表示 arr1 或 arr2 其中至少有一個為空陣列
   * 因此,如果 arr1 不是空陣列,則把它 concat 到 sortedArr 內;
   * 如果是 arr2 中不是空陣列,則把它 concat 到 sortedArr 內。
  **/
  sortedArr = arr1.length ? sortedArr.concat(arr1) : sortedArr.concat(arr2)
  return sortedArr
}

console.log(mergeSort([3, 20, 8, 5, 1, 12, 17, 2]))

圖像化思考

上面這個情況可能會有點難想像實際上的遞回是怎麼執行的,假設我們現在執行函式:
mergeSort([4, 3, 2, 1])
它實際上會先將陣列拆成 [4, 3][2, 1],接著
return sortBeforeMerge(mergeSort[4, 3], mergeSort[2, 1])
這時候遞回函式就需要先去計算出 mergeSort[4, 3]mergeSort[2, 1] 的值。
mergeSort[4, 3] 為例,它則是會先把陣列拆成 [4], [3],接著 return sortBeforeMerge([4], [3]) ,在經過 sortBeforeMerge 的函式時,它會取這兩個陣列當時的第一個元素比較大小,最後會回傳 [3, 4]
同理, mergeSort[2, 1] 在經過 sortBeforeMerge([2], [1]) 之後,會回傳 [1, 2]
如下圖所示:
因此一開始的:
return sortBeforeMerge(mergeSort[4, 3], mergeSort[2, 1])
便會變成:
return sortBeforeMerge([3, 4], [1, 2])
最後便會得到 [1, 2, 3, 4]
如下圖所示:

資料來源

0 意見:

張貼留言