# 2023q1 Homework4 (quiz4)
contributed by < [zeddyuu](https://github.com/zeddyuu) >
## 測驗 `1`
### 程式碼運作原理
----
## 測驗 `2`
### 程式碼運作原理
在看 [incomplete timsort](https://gist.github.com/jserv/2ef9c2c6c274ff738f928f4e5af493a3) 時發現程式碼有錯誤，在 151 行通過 if-else 條件篩過後應該要是 `cmp(cur, next) == 0` 的情況，代表 cur 所指向的值大於 next 所指向的值，接著會用 while 迴圈去找出已經由大到小排序好的區段，但這邊 while 迴圈的條件卻是 `next < last && cmp(cur, next)` ，代表永遠不會進入迴圈執行。
故應該將此段程式碼改為
```c
while (next < last && !cmp(cur, next)) {
++run_len;
cur += size;
next += size;
}
__reverse(first, next, size);
```
有觀察到程式碼內有一些註解要修改避免使用 `alloca()`
```
/* FIXME: avoid alloca */
...
```
不知道原因也不知道跟 `malloc()` 的差別，查詢 [alloca(3)](https://man7.org/linux/man-pages/man3/alloca.3.html) 後發現跟 `malloc()` 使用 heap 來配置空間不同，`alloca()` 會使用到 stack 來配置空間，因為 stack 放的是一些 call function 所需要使用到的東西，像是傳入的參數或是在函式內宣告的參數等等，在函式結束後也會自動釋放掉記憶體，因此 `alloca()` 也不需要配合 `free()` 來釋放記憶體。
:::warning
請愛用 `man` 命令，不用「上網」
:notes: jserv
>了解
:::
聽起來不用搭配 `free()` 去釋放記憶體很方便，但通常別人的程式碼看到都是使用 `malloc()` 搭配 `free()` 使用，鮮少看到 `alloca()`，原因是不像是 `malloca` 一樣在配置空間失敗時會回傳 `NULL`，`alloca()` 回傳的是配置空間的起始位置，若要配置大量空間可能會造成 stack overflow 的問題
>RETURN VALUE
The alloca() function returns a pointer to the beginning of the allocated space. If the allocation causes stack overflow, program behavior is undefined.
故可以將配置記憶體改為使用 `malloc()` 搭配 `free()`
```c
run_t *stack = malloc(sizeof(run_t) * ilog2((last - first) / size) * 2);
...
free(stack);
```
接著看 `timsort()` 中的 `next_partition()`，目的是切出一個一個子序列進行插入排序法，在這個函式裡面有先對於子序列找尋是否有已排序過的區塊，目的應該是為了省略排序已排序過的區塊。
```c
size_t len = next_partition(cur, last, size, cmp);
stack[top].first = cur;
stack[top].last = stack[top].first + len * size;
cur = stack[top].last;
```
之後會用上方配置的 stack 來存放每個切割出來的區塊，且每個區塊都已經排序過，並且檢查是否符合合併的規則，也就是當長度等於 2 時堆疊頂端的區塊長度大於堆疊第二層的區塊長度，長度大於 2 時多添加一個堆疊頂端的區塊長度加上堆疊第二層的區塊長度大於堆疊第三層區塊長度，會這樣設計的原因應該是要讓長度累積到一定量才進行合併，減少 `__merge()` 或是 `__inplace_merge()` 的呼叫次數，如果相反過來堆疊最上方區塊累積少量就進行合併，這種條件下發生的機率會比較大，呼叫的機會也就比較多。
`__merge()` 跟 `__inplace_merge()` 的差別在於需不需要額外的空間來儲存要搬移的變數，而 `__merge()` 是合併排序法的標準做法，兩個已排序的序列元素分別由小比到大，將較小的值放入 buf 中，最後再將其中一個有剩餘元素的序列都放入 buf 尾端，最後再將 buf 的元素都 copy 回去，而 ` __inplace_merge()` 的方式就比較 tricky 一些，是利用排序的大小關係來完成，一樣將兩個排序好的序列比較，決定好最小區塊以及次小區塊之後再利用 `reverse()` 完成部分的排序，最後要移動指標到下一個需要排序的區段。
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> cur1/first1 | <f2> last1 | <f1> cur2/first2 | <f3> last2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 7 | <f3> 8 | <f4> 3 | <f5> 4 | <f6> 5 | <f7> 6"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [color=blue];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
}
```
第一次比較為往右移動 cur1 指標找出比 first2 小的區塊，即 first1 到 cur1 區段
第二次比較為往右移動 cur2 指標找出比 cur1 小的區塊，即 first2 到 cur2 區段
就可以決定出最小區塊跟次小區塊
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first1 | <f7> cur1 | <f2> last1 | <f1> first2 |<f10> cur2 | <f3> last2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 7 | <f3> 8 | <f4> 3 | <f5> 4 | <f6> 5 | <f7> 6"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [color=blue];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f7 -> values:f2;
pointers:f10 -> values:f6;
}
```
剩下兩個區段([ 7，8 ]、[ 5，6 ])沒辦法決定大小，此時就可以先進行 reverse 排序子序列，先反轉 cur1 到 first2 再反轉 first2 到 cur2 可以形成一個由大到小的子序列。
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first1 | <f7> cur1 | <f2> last1 | <f1> first2 |<f10> cur2 | <f3> last2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 8 | <f3> 7 | <f4> 4 | <f5> 3 | <f6> 5 | <f7> 6"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [color=blue];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f7 -> values:f2;
pointers:f10 -> values:f6;
}
```
再反轉 cur1 到 cur2 即完成子序列的排序。
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> first1 | <f7> cur1 | <f2> last1 | <f1> first2 |<f10> cur2 | <f3> last2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 3 | <f3> 4 | <f4> 7 | <f5> 8 | <f6> 5 | <f7> 6"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [color=blue];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f7 -> values:f2;
pointers:f10 -> values:f6;
}
```
此時必定可以保證前段的子序列([ 1，2，3，4 ])為由小到大排序完成，接著就是要以相同演算法排序([ 7，8，5，6 ])，移動指標再跑上述演算法即可，因為排序好的次小區段長度為 first2 - cur2，將 cur1 加上這個長度可以決定下次排序的起始點 first1 ， first2 為當前的 cur2。
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label=" <f2> last1 | <f1> first1/cur1 |<f10> first2/cur2 | <f3> last2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 3 | <f3> 4 | <f4> 7 | <f5> 8 | <f6> 5 | <f7> 6"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [color=blue];
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
pointers:f10 -> values:f6;
}
```
而從圖中可以發現到，last1 在此函式中是不會用到的參數，故可以省略
到這裡可以跑完整個 timsort，由 insertion sort 以及 mergesort 混和的 hybrid sort 演算法。
----
## 測驗 `3`
### 程式碼運作原理
----
Sign in with Wallet
Connect another wallet