2021q1 Homework1 (quiz1)

contributed by < Julian-Chu >

tags: linux2021

程式處理流程

當 pointer to list 為 NULL 直接返回

if(!*list)
    return;

當 pointer to list 不為 NULL 繼續處理

與針對陣列操作的 quicksort 類似，先挑選基準點而後進行比較，這邊利用第一個 node 作為pivot ， 同時把 pivot 與 next node 的連結切斷

node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;

將其他的 node 與 pivot 比較分為兩群 left & right，大於 pivot 放在 right , 其餘放在 left

node_t *left = NULL, *right=NULL;
while(p){
    node_t *n = p;
    p = p->next;
    list_add_node_t(n->value > value ? &right : &left, n);
}

對 left 跟 right，繼續處理，直到 left 跟 right 排好序

    quicksort(&left);
    quicksort(&right);

最後利用 left -> pivot -> right 的順序把 linked list 組合起來

node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;

list_add_node_t 實作上的小差異可能導致

$O(1)$ 與

$O(n)$ 的巨大差異

題目的 list_add_node_t 為

$O(1)$

static inline void list_add_node_t(node_t **list, node_t *node_t){
    node_t->next = *list;
    *list = node_t;
}

如果實作細節是在 list 的 tail.next 加上節點的話，會導致每次都需要走訪 list 所有節點，導致這個函式的時間複雜度為

$O(n)$ ，由於 quicksort 在這一步只需要分成 left 和 right 兩部分， 不需要保持 left 跟 right 的位置或是插入順序 (quicksort 的 unstable 特性)，list_add_note_t 效率更高。

todo: 閱讀 C11 對 inline 跟 static 的敘述

Todo

• random
• non-recusive quicksort
• linux circular doubly-linked list
• A Comparative Study of Linked List Sorting Algorithms