# 2024-03-07 隨堂測驗
> P7?????07

考慮以下針對環狀雙向鏈結串列進行排序的程式碼，使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 來實作 [insertion sort](https://en.wikipedia.org/wiki/Insertion_sort)。

#include <stddef.h>
#include <stdint.h>

#include "list.h"

struct listitem {
    uint16_t i;
    struct list_head list;
};

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;

    return *i1 - *i2;
}

static void list_insert_sorted(struct listitem *entry, struct list_head *head)
{
    struct listitem *item = NULL;

    if (list_empty(head)) {
        list_add(&entry->list, head);
        return;
    }

    list_for_each_entry (item, head, list) {
        if (cmpint(&entry->i, &item->i) < 0) {
            list_add_tail(&entry->list, &item->list);
            return;
        }
    }

    list_add_tail(&entry->list, head);
}

static void list_insertsort(struct list_head *head)
{
    struct list_head list_unsorted;
    struct listitem *item = NULL, *is = NULL;

    INIT_LIST_HEAD(&list_unsorted);
    list_splice_init(head, &list_unsorted);
    /* Put your code here */
    list_for_each_entry_safe(item, &list_unsorted, list) {
        list_del(&item->list);
        list_insert_sorted(item, head);
    }
}

修改上方程式碼，自第 45 行起，使其運作符合預期。

:::warning
改用 `list_for_each_entry_safe` 並呼叫 `list_del` 來處理節點。
:::

TODO:
1. 撰寫測試程式碼，使其得以驗證上述
2. 改寫為 quick sort (部分程式碼列於下方)，重用測試程式碼
3. 將程式碼用於 lab0-c

static void list_qsort(struct list_head *head)
{
    struct list_head list_less, list_greater;
    struct listitem *pivot;
    struct listitem *item = NULL, *is = NULL;
    
    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    pivot = list_first_entry(head, struct listitem, list);
    list_del(&pivot->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            list_move_tail(&item->list, &list_greater);
    }

    list_qsort(&list_less);
    list_qsort(&list_greater);

    /* Put your code here */
    list_splice(&list_less, &pivot);
    list_splice_tail(&list_greater, &pivot);
}