---
tags: linked list, insertion sort, quiz, linux internal, linux2020quiz
---
# [2020q1 第一週測驗題](https://hackmd.io/@sysprog/linux2020-quiz1) 解題思路
contributed by [chses9440611](https://github.com/chses9440611)
* [related code](https://github.com/chses9440611/2020_linux_internal_test)
```cpp
list *sort(list *start) {
if (!start || !start->next)
return start;
list *left = start;
list *right = left->next;
left->next = NULL; // LL0
left = sort(left);
right = sort(right);
for(list *merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
start = merge = left; // LL1
} else {
merge->next = left; // LL2
merge = merge->next;
}
left = left->next; // LL3
} else {
if (!merge) {
start = merge = right; // LL4
} else {
merge->next = right; // LL5
merge = merge->next;
}
right = right->next; // LL6
}
}
return start;
}
```
## Solving thinking
* 首先，先來考慮如何決定 LL0
LL0 有四個選項<br>
```
(a) left->next = NULL
(b) right->next = NULL
(c) left = left->next
(d) left = right->next
```
由第8列和第9列可以知道，排序採取的策略應該跟 **"Divide and Conquer"** 有關 ，而 `right = sort(right)` 會使right 指向一排序好的串列，而 (a) 選項，可以將一 linked list 分成兩個部分。至於 sort 要回傳一個由小到大排好的串列。
若用 \(b\) 選項 `right->next = NULL` 則會在`left = sort(left)` 產生迴圈式的函式呼叫(infinite loop)。
\(c\) 會使left 和 right 指向同一個節點，且 sort(left) 會和 sort(right) 做同樣的事，故不考慮。
\(d\) 會使 left 和 right 因為 sort(left) 和 sort(right)分別指向 n-1 節點中次小和最小的節點，而 start 會指向第 n 個節點，但是觀察後面的程式碼，並沒有 start->data 的比較敘述。故不選擇 \(d\) 選項
* 由於 LL0 為 `left->next = NULL`。則對於一個有 n 個節點的 串列，left 和 right 會分別指到最左邊的節點跟一個有 n-1 節點的 串列，而 sort(right) 會回傳一個由小到大排好的串列。
則接下會有
1. left->data < right->data
2. left->data > right->data
這兩種情形。
附圖是進入迴圈前會有的樣子
由於 merge 的功用應該是找出要執行合併的節點的位置。
因此在第一個 case 中 merge 要跟 left 指向同一個節點。即 LL1 應為
```
(c) merge = left
或
(e) start = merge = left
```
```
start = merge = left -> a -> NULL
right -> b -> c -> ... -> d -> e -> NULL
```
* 接下來，case 1 會執行 LL3，而在 case 1 中，只剩下要怎麼組合 merge 指向的節點和 right 所指向的串列。又 for 迴圈的中止條件為 left 和 right 都要指向 NULL。當下只有 left 可以更動，且 left->next = NULL，所以 LL3 為 `left = left->next`。
```
left = NULL
start = merge -> a -> NULL
right -> b -> c -> ... -> d -> e -> NULL
```
* 繼續執行下去，因為 `left = NULL`，會去執行 LL5，從選項可以知道，LL5負責合併，故選擇`merge->next = right`，至此，case 1 基本上已經完成，接著只要讓 right 指到 NULL 即可完成。
```cpp=23
else {
merge->next = right; // LL5
merge = merge->next;
}
LL6
```
```
left = NULL
start = a -> b -> c -> ... -> d -> e -> NULL
^
merge,right
```
* 因此 LL6 只有 `right = right->next` 可選。因為left 已經指到 NULL 所以不會是 `right = left->next`。
* 到這邊只剩下 LL4 了，接著考慮 case 2的情況，若我們假設 case2 的情況如下：
```
start = left->3
right->1->2->4->5
```
那麼在迴圈中會進入到 LL4的部份，這邊要重新將 start 指向 right 所指向的節點。而且要 merge 的節點會在 right 所指向的串列之中。故 LL4 應為 `start = merge = right`。
```
left -> 3
start = merge = right -> 1 -> 2 -> 4 -> 5
```
* 至此，除了 LL1 的blank 應該都填好了，可以看得出來這是一個串列遞迴版的 [Insertion Sort](https://en.wikipedia.org/wiki/Insertion_sort)
* 繼續，用上述的例子來驗證之前的選擇是否能夠正常運行。
在第二次迴圈前
```
left -> 3
start = merge -> 1 -> 2 -> 4 -> 5
^
right
```
* 接著因為 `left -> data > right -> data` 且 `merge != NULL`，所以進入 line 23-26 的部份。
```cpp=23
else{
merge -> next = right;
merge = merge ->next;
}
right = right -> next;
```
執行完後
```
left -> 3
start -> 1 -> 2 -> 4 -> 5
^ ^
merge right
```
* 進入迴圈之後，因為 `left ->data < right -> data`，會跳到 line 15-18 的地方來執行
```cpp=15
else {
merge->next = left; // LL2
merge = merge->next;
}
left = left->next;
```
執行完後
```
left -> NULL
start -> 1 -> 2 -> 3 -> NULL
^
merge
right -> 4 -> 5 -> NULL
```
* 之後進入後會跳到去執行 line 23-26
```cpp=23
else{
merge -> next = right;
merge = merge ->next;
}
right = right -> next;
```
執行完後是
```
left -> NULL
start -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
^ ^
merge right
```
* 至此，排序已經完成，進入迴圈再次執行 line 23-26 直到 right 指向 NULL
```cpp=23
else{
merge -> next = right;
merge = merge ->next;
}
right = right -> next;
```
執行完後會是
```
left -> NULL
start -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
^ ^
merge right
```
* 最後因為 left 和 right 都指向 NULL，不會再進入迴圈，驗證正確。
## Explanation
遞迴式的Insertion Sort
1. 將 n 個結點的串列分成一個節點和一 n-1 個節點的串列，分別用 left 和 right 去指向
2. right = sort(right) 回傳一個已排序好的串列
3. 比較 left 和 right 所指的節點的大小，較小的節點為 start ，並將 left 所指向的節點用 Insertion Sort 的方式插入到正確的位置
## LL1 的選擇
* LL1有兩種可能選擇，`(c) merge = left` 或是 `(e) start = merge = left`，而答案給的是後者，但是在一開始，start 跟 left 是指向同一個節點。而start 只需要在回傳的 right 所指向的節點小於 left 所指向的節點才需要重新指向 right。所以兩者的答案都不會改變結果。
* 除了是避免在運行過程中 start 因不可預期的錯誤導致指到 undefined 的地方，那 \(e\) 會是比 \(c\)好的選項。
* 所以我也用不同的選項分別去執行來看出是否有所不同
```cpp=
if (version == 0)
start = merge = left;
else
merge = left;
```
* 利用產生 100 組 10 個亂數的數字串列，每組分別有兩個一樣的串列 head 和 head2，分別去做不同選項的排序。
所得結果如下：
```
...
-----------------------
The array numbers are: 37 34 4 12 39 92 7 87 97 72
Queue1 after sort: 4 7 12 34 37 39 72 87 92 97
Queue2 after sort: 4 7 12 34 37 39 72 87 92 97
Are two queues same?
Same queues
-----------------------
The array numbers are: 16 36 34 73 24 70 23 63 95 20
Queue1 after sort: 16 20 23 24 34 36 63 70 73 95
Queue2 after sort: 16 20 23 24 34 36 63 70 73 95
Are two queues same?
Same queues
-----------------------
The array numbers are: 36 81 5 54 41 18 72 8 72 82
Queue1 after sort: 5 8 18 36 41 54 72 72 81 82
Queue2 after sort: 5 8 18 36 41 54 72 72 81 82
Are two queues same?
Same queues
-----------------------
The total scores: 100/100
```
由此可見，LL1 應有兩個答案。
## Usage of cppcheck
使用 cppcheck 來做靜態檢查
`cppcheck --enable=all main.c qsort.c qsort.h`
輸出如下:
```
Checking main.c ...
main.c:15:7: style: The scope of the variable 'numbers' can be reduced. [variableScope]
int *numbers, i, scores;
^
main.c:16:8: style: The scope of the variable 'q_head' can be reduced. [variableScope]
list *q_head, *q_tail, *q_head2, *q_tail2;
^
main.c:16:17: style: The scope of the variable 'q_tail' can be reduced. [variableScope]
list *q_head, *q_tail, *q_head2, *q_tail2;
^
main.c:16:26: style: The scope of the variable 'q_head2' can be reduced. [variableScope]
list *q_head, *q_tail, *q_head2, *q_tail2;
^
main.c:16:36: style: The scope of the variable 'q_tail2' can be reduced. [variableScope]
list *q_head, *q_tail, *q_head2, *q_tail2;
^
1/3 files checked 47% done
Checking qsort.c ...
qsort.c:23:8: style: The scope of the variable 'tmp' can be reduced. [variableScope]
list* tmp;
^
2/3 files checked 92% done
Checking qsort.h ...
3/3 files checked 100% done
qsort.c:43:0: style: The function 'q_compare' is never used. [unusedFunction]
^
nofile:0:0: information: Cppcheck cannot find all the include files (use --check-config for details) [missingIncludeSystem]
```
* 大都是將變數宣告跟賦值分開寫的問題，所以會出現 variable scope 的 reduced 建議
* qsort.c 有一個 q_compare function ，這個是用來檢測 sort() 回傳的串列的排序和經過 bubble_sort 的整數陣列是否一致，後來驗證過後，把 main.c 中關於 q_compare 的敘述拿掉了。所以出現 unusedFunction 的回報。
* 使用 --supress=missingIncludeSystem 來避免找不到 include files 的訊息
經修正後使用`cppcheck --enable=all --supress=missingIncludeSystem *.[ch]`
結果如下:
```
Checking main.c ...
1/3 files checked 48% done
Checking qsort.c ...
2/3 files checked 93% done
Checking qsort.h ...
3/3 files checked 100% done
```
## Usage of [infer](https://fbinfer.com)
* 使用 infer 發現能夠找出 cppcheck 不一定會回報的問題。
```
infer run -- gcc -c main.c qsort.c qsort.h
```
然後出現以下錯誤和一堆紅字：
```
Capturing in make/cc mode...
main.c:22:25: error: use of undeclared identifier 'q_tail2'; did you mean 'q_tail'?
list *q_tail = *q_tail2 = NULL;
^~~~~~~
q_tail
main.c:22:15: note: 'q_tail' declared here
list *q_tail = *q_tail2 = NULL;
^
main.c:22:33: error: assigning to 'list' (aka 'struct __list') from incompatible type 'void *'
list *q_tail = *q_tail2 = NULL;
^ ~~~~
main.c:24:38: error: use of undeclared identifier 'q_tail2'; did you mean 'q_tail'?
list *q_head2 = q_insert_lot(q_tail2, numbers, LENGTH);
^~~~~~~
q_tail
main.c:22:15: note: 'q_tail' declared here
list *q_tail = *q_tail2 = NULL;
^
3 errors generated.
Error: the following clang command did not run successfully:
...
```
看了之後，發現是 q_tail2 宣告的問題，這種寫法是無效的。將其改為
```
list *q_tail, *q2_tail;
q_tail = q2_tail = NULL;
```
也改正其他位置的錯誤。
* 再次執行 infer 的檢查
得到如下訊息
```
Found 2 issues
qsort.c:8: error: NULL_DEREFERENCE
pointer `tmp` last assigned on line 7 could be null and is dereferenced at line 8, column 5.
6. {
7. list *tmp = malloc(sizeof(list));
8. > tmp->data = d;
9. tmp->next = NULL;
10. return tmp;
main.c:66: error: NULL_DEREFERENCE
pointer `tmp` last assigned on line 63 could be null and is dereferenced at line 66, column 9.
64. int i;
65. for (i = 0; i < size; i++)
66. > tmp[i] = rand() % 100;
67.
68. return tmp;
Summary of the reports
```
這邊是因為 tmp 有可能有 NULL_DEREFERENCE 的問題，我這邊透過增加 if 敘述來處理，即因為 malloc 失敗的話就會回傳 NULL。較好的方式應該是寫例外處理的函式來進行。
* 修正到沒有 NULL deference 的問題後，可得如下
```
Capturing in make/cc mode...
Found 3 source files to analyze in /home/jason/Project/2020_Linux_Internal/ttt/2020_linux_internal_test/infer-out
Analysis finished in 4.517ss
```
* 使用 infer 會在目前目錄中產生 infre-out 的資料夾，會將檢查的報告在 bugs.txt 這個檔案中。
## Feedback
若有想要問的或是哪裡的敘述寫得不足或是不清楚的地方，可以在下面直接編輯。
ex:
- [ ] 延伸問題勒
延伸問題
===
1. 解釋上述程式運作原理;
2. 指出程式改進空間，特別是考慮到 Optimizing merge sort;
3. 將上述 singly-linked list 擴充為 circular doubly-linked list 並重新實作對應的 sort;
4. 依循 Linux 核心 include/linux/list.h 程式碼的方式，改寫上述排序程式;
5. 嘗試將原本遞迴的程式改寫為 iterative 版本;
Sign in with Wallet
Connect another wallet