# 2023q1 Homework1 (quiz1)
contributed by < [`tintinjian12999`](https://github.com/tintinjian12999) >
## 測驗一
### 解釋程式碼運作原理
本題節點的結構如下

#include <stdint.h>
#include "list.h"

struct item {                         
    uint16_t i;
    struct list_head list;
}

觀察 `list.h` 裡有關 `list_first_entry()` 的敘述

/**
 * list_first_entry() - Get first entry of the list
 * @head: pointer to the head of the list
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 *
 * Return: @type pointer of first entry in list
 */
#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

可以知道

    struct item *pivot = list_first_entry(head, AAA, BBB);
    list_del(&pivot->list);

裡的 AAA 與 BBB 應分別為 item 與 list ，這裡將 linked list 的第一筆資料放入 pivot 當中。

    struct item *itm = NULL, *is = NULL;
    CCC (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            DDD (&itm->list, &list_less);
        else
            EEE (&itm->list, &list_greater);
    }

接著對 linked list 裡的資料與 pivot 做比較，若較大則放入 `list_greater` ，較小則放入 `list_less` ，這裡的 CCC 在因為需要走訪每筆資料且在執行過程中資料會被移動應為 `list_for_each_entry_safe` ， DDD 與 EEE 在參考[課堂問答簡記](https://hackmd.io/VIvUZemESvGUev4aCwOnWA?view)和[`chun61205`](https://hackmd.io/CPq4_owmTdGLEdPdqtbGeg)的想法與[cin-cout](https://hackmd.io/@IFhfI6MRSZSja7n1T2-DNg/r1VumPi0o)的圖例後知道應為 `list_move_tail`。

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    FFF(&list_greater, head);

最後的 FFF 因為要將大的接在後面故使用的是 `list_splice_tail` 。
## 測驗二
### 解釋程式碼運作原理
這裡將 quick sort 改為疊代的方式實現

    GGGG (itm, is, &partition, list) {
        list_del(&itm->list);
        if (cmpint(&itm->i, &pivot->i) < 0)
            list_move(&itm->list, &list_less);
        else
            list_move(&itm->list, &list_greater);
    }

這邊同樣是做 itm 與 pivot 值的比較，若大於則放進 list_greater ，小於則放進 list_less ，因此 GGGG 應同樣為走訪每筆資料的 `lis_for_each_entry_safe` 。

HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, JJJJ);

參考[Jerejere0808](https://hackmd.io/Fb_-zLB0S_K7JGpdiOBLMQ?view)的解說知道 HHHH 應為 `list_move_tail` ， IIII 和 JJJJ 為 &stack[++top]。