# 2020q3 Homework1 (lab0)
contributed by < bitter-bits >

## 開發環境

# OS:
Microsoft Windows 10.0.18363 Build 18363

# WSL/Linux
Linux DESKTOP-2EA14PB 4.4.0-18362-Microsoft #1049-Microsoft Thu Aug 14 12:01:00 PST 2020 x86_64 x86_64 x86_64 GNU/Linux

# gcc version
gcc version 9.3.0 (Ubuntu 9.3.0-10ubuntu2)

## 好難啊

一開始就撞到牆。

在實作 ```q_insert_head()``` 發現不能用 ```strcpy()``` ，會在 ```git commit``` 時被擋下，原因是安全性問題。

改成 ```strncpy()``` 就可以 ```git commit``` ，沒想到一執行就失敗：

$ make valgrind
ERROR: Removed value dolphinU��� != expected value dolphin
ERROR: Removed value bearU��� != expected value bear
ERROR: Removed value gerbilU��� != expected value gerbil

後來才想到是字串的最後面要補 ```NULL``` 。

## 重寫 q_sort()

執行 ```make test``` 出現錯誤訊息，抱怨排序的部分效率不好：

因為原來的版本是實作 insertion-sort ， big-O 是 N<sup>2</sup> ：

list_ele_t *a = q->head;
while (a) {
list_ele_t *b = a->next;
while (b) {
if (strcmp(a->value, b->value) > 0) {
char *t = a->value;
a->value = b->value;
b->value = t;
}
b = b->next;
}
a = a->next;
}

後來想利用

#include <stdlib.h>

裡面提供的 quick sort ：

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

但是在準備 ```base``` 來存放 ```list_ele_t*[]``` 的時候，被 ```qtest``` 擋下來，表示這裡不可以使用 ```malloc``` 。

花了兩天終於寫好 in-place 的版本。最後執行```make test``` 出現：

--- TOTAL 88/100

真是感動到不行啊！繼續改進到 100 。