# 2021q1 Homework1 (quiz1)
contributed by < `Jings1017` >
###### tags: `linux2021`
> [測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)

## 解析

### node 結構定義

typedef struct __node{
    int value;
    struct __node *next;
} node_t

此題所定義的 node 結構及連接方式如下圖所示

digraph SLL{
    rankdir = LR
    head [shape=record, label="head"]
    node1 [shape=record, label="{A|{<value>value}|<next>next}"];
    node2 [shape=record, label="{B|{<value>value}|<next>next}"];
    
    head:e -> node1:w;
    node1:next:e-> node2:w;

}

### list_add_node_t

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

下圖中， node_t 為欲插入的新節點，
首先將 list 整個接到 node_t 之後方，
再把 node_t 令為新串列之 head (紅色 head )

digraph structs{
    rankdir=LR;
    node[shape=box];
    node1[label=node_t color=red];
    {
        head0[label="head" shape=plaintext,fontcolor=blue]
        head1[label="head" shape=plaintext,fontcolor=red]
        list0[label=A];
        list1[label=B];
        list2[label=C];
    }
    {
        rank="same"
        head0->list0
        
    }
    {
        rank = "same"
        head1->node1
    }
    node1->list0->list1->list2
}

### list_concat

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);
    *left = right;
}

這一部份的程式碼主要是先找到 list 最後一個 node 的 next，再將 *left 指向上述之位置

digraph structs {
    rankdir=LR;
    node[shape=box];
    left[label= "*left" shape= plaintext, fontcolor=blue];
    null[label= "NULL" shape= plaintext];
    n1[label= "a1"];
    n2[label= "a2"];
    n3[label= "a3"];
    {
        rank="same";
        left->null;
    }
    n1->n2->n3->null;
}

最後再把 *left 指向 right，如此一來就可將 left 與 right 串連在一起

digraph structs {
    rankdir=LR;
    node[shape=box];
    left[label= "*left" shape= plaintext, fontcolor=blue];
    l1[label= "a1"];
    l2[label= "a2"];
    l3[label= "a3"];
    r1[label= "b1" color=red];
    r2[label= "b2" color=red];
    {
        rank="same";
        left->r1;
    }
    l1->l2->l3->r1->r2;
}

### quicksort

void quicksort(node_t **list)
{
    if (!*list)
        return;

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

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

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

    node_t *result = NULL;
    list_concat(&result, left);
    CCC;
    *list = result;
}

### AAA = ? / BBB = ?

&right / &left

根據 `list_add_node_t(n->value > value ? AAA : BBB, n); ` 可知若目前的 value 大於 pivot 之值，則放入 right ，反之，若小於 piovt 之值，則放入 left 。
又因為 list_add_node_t() 函式中使用 node_t ** ，故 `AAA = &right` , `BBB = &left`

### CCC = ?

list_concat(&result, pivot);
list_concat(&result, right);

在此處主要是做串接，由左到右的順序為 left, pivot, right , 故在此填入 `list_concat(&result, pivot);`, `list_concat(&result, right);`

## 延伸問題

### Non-Recursive Quick Sort

參考 [Optimized QuickSort](https://alienryderflex.com/quicksort/) 實作 non-recursive quick sort
想法是先選定 pivot ，這裡用最左方的元素當作 pivot ，
然後 L, R 是欲排序的範圍，其中 L 表最左，R 表最右，
用 pivot 和此範圍中每個元素比較。
若從 R 往左開始，比 pivot 小的 放到 arr[L]，再做 L++，
若從 L 往左開始，比 pivot 大的 放到 arr[R]，再做 R++


#### 程式碼 A

void quicksort_NR(node_t **list){
    
    /* put list in the arr */
    node_t *ptr = *list;
    int arr[NUM_SIZE], cnt=0;
    while(ptr){
        arr[cnt++] = ptr->value;
        ptr = ptr->next;
    }
    free(ptr);

    int pivot, L, R;
    int beg[NUM_SIZE], end[NUM_SIZE];
    cnt = 0;
    beg[0] = 0;
    end[0] = NUM_SIZE;
    while(cnt>=0){
        L = beg[cnt];
        R = end[cnt]-1;
        if(L<R){
            pivot = arr[L];
            if(cnt == NUM_SIZE-1)
                return ;

            while(L<R){
                while(arr[R] >= pivot && L<R){
                    R--;
                }
                if(L<R){
                    arr[L++] = arr[R];
                }

                while(arr[L] <= pivot && L<R){
                    L++;
                }
                if(L<R){
                    arr[R--] = arr[L];
                }    
            }
            
            arr[L] = pivot;
            int tmp = end[cnt];
            end[cnt] = L;
            cnt++;
            beg[cnt] = L+1;
            end[cnt] = tmp;
        }
        else{
            cnt--;
        }
    }

    /* update the list */
    node_t *pointer = *list;
    cnt = 0;
    while(pointer){
        pointer->value = arr[cnt++];
        pointer = pointer->next;
    }
    free(pointer);
}