# 2021q1 Homework1 (lab0)
contributed by < `ch1p98` >

<style>
.question {
color:rgb(184, 126, 139)
}
</style>

## 作業要求

## 開發記錄
:::danger
注意作業規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::

### 關於insert的函式：

x = strlen(value);
char *val = malloc(x + 1);
memcpy(val, s, x);
val[x] = '\0';

若沒有最後一行，寫入時會出現類似如下錯誤：

ERROR: Removed value dolphinUU??? != expected value dolphin

* !與NULL:

if (!q)
if (q == NULL)

這兩個判斷句的執行結果是一樣的。

* ~~個人目前的結論是printf比gdb好用。大概是我還沒弄懂gdb~~
* 還要找時間研究GDB。
:::danger
你既然說自己沒弄懂 gdb，何以有立場說 printf 比 GDB 好用呢？
:notes: jserv
:::

:::success
我錯了，今天突然就懂gdb怎麼下指令了。前一天腦袋抽筋才看不懂指令。
今天printf和gdb都有幫助到我；gdb backtrace, frame等指令幫助我找到出錯的位置，且能夠step，就像一般的IDE一樣，但這有時候會造成正常執行時不會出現的time limit exceeded。
printf有時在想要同時觀察數行程式碼且只要稍微看一下時，使用上會快一點，而且"比較"不會造成time limit exceeded的問題。
:::

* 程式碼應該邊寫邊整理，例如：

if (q->size != 0) { 
        q->tail->next = newt;
        newt->next = NULL;
    } else {
        q->head = newt;
        newt->next = NULL;
    }
    q->tail = newt;

其實應該整理成這樣：

if (q->size != 0) { /*if q is not empty.*/
        q->tail->next = newt;
    } else
        q->head = newt;
    newt->next = NULL;
    q->tail = newt;

但我一直執著於寫出正確的邏輯，想要修正邏輯的部分後再整理。結果苦思良久，最後忍不住動手邊整理邊修改，修改好了以後，正確的邏輯也就浮現了。

### q_sort
* 因為先前就有同學在課堂提到quick sort效能會受到測資影響，worst case下可能出現$O(n^2)$的運行結果：若pivot每次都選固定位置，例如頭或尾。假設該子序列max/min value全部或相當比例出現在此處就會變成或接近$O(n^2)$。雖然可以用隨機取、平均取pivot position等方法避免，但這樣也增加實作的複雜度。
* 因此決定以merge sort實作。

strcmp(s->value, e->value) < 0  /*correct*/
s->value < e->value     /*incorrect*/

拜託，這個坑不要踩第二次......我的4小時...
第二個是拿address相減。
python也沒這種寫法；要是直接拿字串相減會報錯。(雖然我也是剛剛開colab才確定這件事)
***<span class = question>你到底為什麼一開始會想要這樣寫？</span>***

總之依照樣版實作總算是達到<font color = "c90c0c">94</font>/100

* input