pseudocode詳細解釋
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
| Merge(arr_1[], arr_2[]){
p 為 arr_1[]的起始 index;
q 為 arr_2[]的起始 index;
while(arr_1 && arr_2 尚未scan完畢){
if (p.data < q.data) then{
p.data 先輸出到一個新的 array;
p = p + 1;
}
else{
q.data 先輸出到一個新的 array;
q = q + 1;
}
while(arr_1尚未scan完畢){
複製 arr_1 剩下的 data 到新的 array 裡;
}
while(arr_2尚未scan完畢){
複製 arr_2 剩下的 data 到新的 array 裡;
}
}
}
MergeSort(A[], head, tail){
if(head < tail){
mid = (head + tail) / 2;
MergeSort(arr, head, mid);
MergeSort(arr, mid+1, tail);
Merge(arr, head, mid, tail);
}
}
|
第一部分:Merge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| Merge(arr_1[], arr_2[]){ //arr_1是左相鄰陣列,arr_2是右相鄰陣列
p 為 arr_1[]的起始 index;
q 為 arr_2[]的起始 index;
while(arr_1 && arr_2 尚未scan完畢){
if (p.data < q.data) then{ //若是p.data的值較小
p.data 先輸出到一個新的 array;
p = p + 1;
}
else{ //若是q.data的值較小
q.data 先輸出到一個新的 array;
q = q + 1;
}
while(arr_1尚未scan完畢){
複製 arr_1 剩下的 data 到新的 array 裡;
}
while(arr_2尚未scan完畢){
複製 arr_2 剩下的 data 到新的 array 裡;
}
}
}
|
第一個while中，我們首先會將原始陣列分為左右兩半，並字左右陣列的第一index的”值”依序比較大小並放入新的arr(目標陣列)中。而在第二個while中我們所做的就是將未比對到的陣列先copied進目標arr中表示待比較。而merge主要做的便是”比較、結合”的兩個動作。
第二部分:merge sort
1
2
3
4
5
6
7
8
| MergeSort(A[], head, tail){
if(head < tail){
mid = (head + tail) / 2;
MergeSort(arr, head, mid);
MergeSort(arr, mid+1, tail);
Merge(arr, head, mid, tail);
}
}
|
在MergeSort的副程式中，我們定義了頭、尾與中間點，而MergeSort就是以迴圈方式，不斷的定義左右兩塊與重複執行merge的動作直到目標陣列建立完成。
題目:merge sort實作
運用C++語言來實做merge sort!
解法
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <iostream>
#include <vector>
const int Max = 1000;
void Merge(std::vector<int> &Array, int front, int mid, int end){
// 利用 std::vector 的constructor,
// 把array[front]~array[mid]放進 LeftSub[]
// 把array[mid+1]~array[end]放進 RightSub[]
std::vector<int> LeftSub(Array.begin()+front, Array.begin()+mid+1),
RightSub(Array.begin()+mid+1, Array.begin()+end+1);
LeftSub.insert(LeftSub.end(), Max); // 在LeftSub[]尾端加入值為 Max 的元素
RightSub.insert(RightSub.end(), Max); // 在RightSub[]尾端加入值為 Max 的元素
int idxLeft = 0, idxRight = 0;
for (int i = front; i <= end; i++) {
if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
Array[i] = LeftSub[idxLeft];
idxLeft++;
}
else{
Array[i] = RightSub[idxRight];
idxRight++;
}
}
}
void MergeSort(std::vector<int> &array, int front, int end){
// front與end為矩陣範圍
if (front < end) { // 表示目前的矩陣範圍是有效的
int mid = (front+end)/2; // mid即是將矩陣對半分的index
MergeSort(array, front, mid); // 繼續divide矩陣的前半段subarray
MergeSort(array, mid+1, end); // 繼續divide矩陣的後半段subarray
Merge(array, front, mid, end); // 將兩個subarray做比較, 並合併出排序後的矩陣
}
}
void PrintArray(std::vector<int> &array){
for (int i = 0; i < array.size(); i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {26,5,77,61,11,59,15,48,19};
std::vector<int> array(arr, arr+sizeof(arr)/sizeof(int));
std::cout << "original:\n";
PrintArray(array);
MergeSort(array, 0, 8);
std::cout << "sorted:\n";
PrintArray(array);
return 0;
}
|
解釋與詳細介紹
第一部分:merge
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
| void Merge(std::vector<int> &Array, int front, int mid, int end){
// 利用 std::vector 的constructor,
// 把array[front]~array[mid]放進 LeftSub[]
// 把array[mid+1]~array[end]放進 RightSub[]
std::vector<int> LeftSub(Array.begin()+front, Array.begin()+mid+1),
RightSub(Array.begin()+mid+1, Array.begin()+end+1);
LeftSub.insert(LeftSub.end(), Max); // 在LeftSub[]尾端加入值為 Max 的元素
RightSub.insert(RightSub.end(), Max); // 在RightSub[]尾端加入值為 Max 的元素
int idxLeft = 0, idxRight = 0;
for (int i = front; i <= end; i++) {
if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
Array[i] = LeftSub[idxLeft];
idxLeft++;
}
else{
Array[i] = RightSub[idxRight];
idxRight++;
}
}
}
|
在Merge()中，我們用LeftSub 和 RightSub的方式定義了左子陣列和右子陣列，左代表了原始arr自頭到中(array[front]array[mid])、右則代表了中到後(array[mid+1]array[end])。
而這裡我們用到了C++ 的vector作為容器(container)，可以先將其想為一個使用上更方便的array，若之後有時間我們再進行介紹!
1
2
| LeftSub.insert(LeftSub.end(), Max); // 在LeftSub[]尾端加入值為 Max 的元素
RightSub.insert(RightSub.end(), Max); // 在RightSub[]尾端加入值為 Max 的元素
|
這兩行分別是在左右兩子陣列中的末端(.end()是末端的意思)加上(.insert()是插入數值的意思)一個Max值作為最尾端的表示，因為沒有數值會大於最大值，所以我們可以藉由插入的Max去確認兩子陣列到達最末端。而這題因為我們採用的是固定值的陣列，自行設定的Max是1000(或是也可以用INT_MAX代替)。
1
2
3
4
5
6
7
8
9
10
11
| for (int i = front; i <= end; i++) {
if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
Array[i] = LeftSub[idxLeft];
idxLeft++;
}
else{
Array[i] = RightSub[idxRight];
idxRight++;
}
}
|
for迴圈部分採用了以i變數來循序比較數值，並將較小的質優先放入目標array直到結束(因為先放入的元素會在較前面，以達成從小排序到大的目的)。
第二部分:MergeSort
1
2
3
4
5
6
7
8
9
| void MergeSort(std::vector<int> &array, int front, int end){
// front與end為矩陣範圍
if (front < end) { // 表示目前的矩陣範圍是有效的
int mid = (front+end)/2; // mid即是將矩陣對半分的index
MergeSort(array, front, mid); // 繼續divide矩陣的前半段subarray
MergeSort(array, mid+1, end); // 繼續divide矩陣的後半段subarray
Merge(array, front, mid, end); // 將兩個subarray做比較, 並合併出排序後的矩陣
}
}
|
MergeSort的部分便是用if迴圈不斷判斷與重複分出前半、後半arr的動作並持續merge出最終陣列的順序。
第三部分:PrintArray與main函式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void PrintArray(std::vector<int> &array){
for (int i = 0; i < array.size(); i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {26,5,77,61,11,59,15,48,19};
std::vector<int> array(arr, arr+sizeof(arr)/sizeof(int));
std::cout << "original:\n";
PrintArray(array);
MergeSort(array, 0, 8);
std::cout << "sorted:\n";
PrintArray(array);
return 0;
}
|
我們設置了一個PrintArray()函式來輸出結果；而在main函式中我們定義了昨天舉例的陣列為固定值的arr[]作為示範，並用vector設置陣列大小(array)與輸出排序前(origin)與排序後(sorted)的數列值。
第四部分:成果展示
是不是跟插入排序法的方式不太一樣呢?那我們明天見!ヽ(=^･ω･^=)丿!
參考資料:
https://kopu.chat/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F-merge-sort/
https://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html
https://mropengate.blogspot.com/2015/07/cc-vector-stl.html