2024q1 Homework2 (quiz1+2)

contributed by < Grace258 >

• 第 1 週測驗題
• 第 2 週測驗題

---

測驗 1

實作非遞迴 (non-recursive) 的快速排序法，以 swap 為主體，利用 L 與 R 去紀錄需交換的數量，再用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍。

node_t *list_tail(node_t **left)

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &((*left)->next); //AAAA
    return *left;
}

將 *left 移到鏈結串列的最後一個節點，因為使用 indirect pointer 所以要加上 & 取得指標的位址。

#4 left = &((*left)->next);

---

int list_length(node_t **left)

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &((*left)->next); //BBBB
    }
    return n;
}

將 *left 移到鏈結串列的最後端 (NULL) ，因為使用 indirect pointer 所以要加上 & 取得指標的位址。

#6 left = &((*left)->next);

---

void quick_sort(node_t **list)

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = p->next;    //CCCC
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = list_tail(&left);    //DDDD
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&right);    //EEEE

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

使用指標 n 走遍整個鏈結串列，將除了 head/pivot 節點的剩餘部分分成鏈結串列 right 和鏈結串列 left ，並將這三個鏈結串列的指標放入 stack(begin 和 end) 中。

將整個鏈結串列分成 pivot 、 left 、 right 三個部分( left 放小於 pivot 的節點， right 放大於 pivot 的節點)

重複執行直到 left 、 right 、pivot 都排序完畢。

改進方案

void quick_sort(struct list_head *head) {
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head *pivot = list_entry(head->prev, struct list_head, list);
    struct list_head *left_list, *right_list;
    INIT_LIST_HEAD(&left_list);
    INIT_LIST_HEAD(&right_list);

    struct list_head *pos, *q, *entry;
    list_for_each_safe(pos, q, head) {
        struct list_head *tmp = list_entry(pos, struct list_head, list);
        if (tmp != pivot) {
            list_del(pos);
            INIT_LIST_HEAD(pos);
            if (tmp->value < pivot->value){
                list_for_each_entry(entry, left_list, list) {
                    if (tmp->value < entry->value) {
                        list_add_tail(&tmp->list, &entry->list);
                        return;
                    }
                }
                list_add_tail(&tmp->list, &left_list);
            }
                
            else{
                list_for_each_entry(entry, right_list, list) {
                    if (tmp->value < entry->value) {
                        list_add_tail(&tmp->list, &entry->list);
                        return;
                    }
                }
                list_add_tail(&tmp->list, &right_list);
            }                
        }
    }

    quick_sort(&left_list);
    quick_sort(&right_list);
    list_splice_tail(&left_list, head);
    list_add_tail(&pivot->list, head);
}

測驗 2 Timsort