PJCHENder 未整理筆記

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

2017-09-26

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

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

問題描述

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

前置知識:Merge Sort

Merge Sort 和 Bubble Sort 一樣,都是一種用來排序的演算法。

Merge Sort 的演算法主要包含兩個部分:

1. 將陣列對半拆分

Merge Sort 的第一步是要將陣列兩兩對半拆分,直到拆到每個陣列只剩一個元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 原本的陣列
[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.將陣列排序後加以合併

我們把上面拆分好的陣列,兩兩一組開始進行排序,每次排序時都是取該陣列的++第一個元素++進行比較:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 拆分好的陣列
[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)
];

兩兩比較後排序的方式可以參考下圖,每次比較都是取各陣列的第一個元素來進行比較:

圖片來源:Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy

整個合併排序法如下圖所示:

wiki

圖片來源:合併排序 @ wikipedia

因此我們一共需要兩個函式,並且一樣會透過遞回函式的方式來處理:

1
2
3
4
5
6
7
8
9
10
11
function mergeSort(arr) {
// 接受一組尚未排序的陣列當作參數,將它們對半切分
}

function sortBeforeMerge(arr1, arr2) {
/**
* 代入兩個已經各自排序過的陣列
* 每次都取這兩個陣列中當時的第一個元素進行比較
* 把數值小的放前面,最後合併成一個陣列
**/
}

Merge Sort 這個演算法我覺得稍微有一點點小小複雜,非常需要圖像化來幫助思考,但我們可以先看 code ,看完之後會更瞭解它實際上的運作方式。

演算法實做

1. 將陣列進行對半切分

首先要將傳進來的陣列進行對半切分,這裡可以透過 Array.prototype.slice 來進行:

1
2
3
4
5
6
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 中:

1
2
3
4
5
6
7
8
9
10
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);
}
}

:::info
Array.prototype.shift() 可以把移除陣列中的第一個元素,並把它存出來。
:::

經過 while 迴圈後,我們會得到一組已經經過 merge sort 方式排序好的陣列;另外,while 迴圈終止的條件是只要 arr1 或 arr2 其中一組為空陣列時就會停止,因此這時候 arr1 或 arr2 其中有一組還不是空陣列,我們要把不為空陣列的陣列透過 Array.prototype.concat 連接到 sortedArr 後面。

由於我們傳進 sortBeforeMerge 這個函式的陣列是已經經過排序的,因此,可以確定透過 concat 連結好的陣列,其數值也會是由小到大的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 這個函式結合遞回的概念,在使用遞回函式時,一定要記得設定終止條件:

1
2
3
4
5
6
7
8
9
10
11
12
function mergeSort(arr) {
// 遞回函式終止條件:當陣列被拆到只剩一個元素時
if (arr.length <= 1) {
return arr;
}

// 接受一組尚未排序的陣列當作參數,將它們對半切分
// ...

// 遞回函式
return sortBeforeMerge(mergeSort(firstHalf), mergeSort(secondHalf));
}

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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]))

Algorithm: Merge Sort @ repl.it

圖像化思考

上面這個情況可能會有點難想像實際上的遞回是怎麼執行的,假設我們現在執行函式:

1
mergeSort([4, 3, 2, 1]);

它實際上會先將陣列拆成 [4, 3][2, 1],接著

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]

如下圖所示:

圖片來源:Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy

因此一開始的:

1
return sortBeforeMerge(mergeSort[(4, 3)], mergeSort[(2, 1)]);

便會變成:

1
return sortBeforeMerge([3, 4], [1, 2]);

最後便會得到 [1, 2, 3, 4]

如下圖所示:

圖片來源:Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy

資料來源

掃描二維條碼,分享此文章