# 2021q1 Homework1 (quiz1)
contributed by < `cyrong` >

## 第一周測驗題 (quiz1)
### 答案
1. LLL = `(c)` `left = &((*left)->next)`
2. AAA = `(e)` `&right`
3. BBB = `(c)` `&left`
4. CCC = `(b)` `list_concat(&result, pivot); list_concat(&result, right)`
### 作答後的程式碼

考慮一個單向 linked list，其結構定義為:

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

已知不存在 circular (環狀結構)，下方程式碼嘗試對該單向 linked list 進行 Quick sort，預期依據遞增順序。

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

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

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 ? &right : &left, n);
    }

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

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

## 測試用程式

static bool list_is_ordered(node_t *list) {
    bool first = true;
    int value;
    while (list) {
        if (first) {
            value = list->value;
            first = false;
        } else {
            if (list->value < value)
                return false;
            value = list->value;
        }
        list = list->next;
    }
    return true;
}

static void list_display(node_t *list) {
    printf("%s IN ORDER : ", list_is_ordered(list) ? "   " : "NOT");
    while (list) {
        printf("%d ", list->value);
        list = list->next;
    }
    printf("\n");
}

int main(int argc, char **argv) {
    size_t count = 20;

    node_t *list = NULL;
    while (count--)
        list = list_make_node_t(list, random() % 1024);

    list_display(list);
    quicksort(&list);
    list_display(list);

    if (!list_is_ordered(list))
        return EXIT_FAILURE;

    list_free(&list);
    return EXIT_SUCCESS;
}

添加題目中沒有的 `list_make_node_t`

node_t *list_make_node_t(node_t *list, int value)
{
    node_t *n;
    n = malloc(sizeof(node_t));
    if (!n)
        return list;
    n->value = value;
    n->next = list;
    return n;

}

## 程式運作原理
`count` 用來決定 list 中有多少個 node
接著利用 `random() % 1024` 產生 node 之 value
先展示未處理之 list 接著對 list 作 quicksort 再展示一次
最後驗證sort是否正確
## 視覺化展現
對以下範例 list 作此 quicksort

digraph foo {
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> 12 | <ref> }"];
    b [label="{ <data> 99 | <ref> }"];
    c [label="{ <data> 37 | <ref> }"];
    d [label="{ <data> 5  | <ref> }"];
    e [label="{ <data> 17 | <ref> }"];
    a:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false];
    b:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> d:data [arrowtail=dot, dir=both, tailclip=false];
    d:ref:c -> e:data [arrowtail=dot, dir=both, tailclip=false];
}

抓 `list->head` 作為 pivot

digraph foo {
    node [shape=record];
    rankdir=LR;
    
    ordering=out;
    subgraph cluster {
        label="pivot"
        a [label="{ <data> 12 | <ref> }"];
    }    
    b [label="{ <data> 99 | <ref> }"];
    c [label="{ <data> 37 | <ref> }"];
    d [label="{ <data> 5  | <ref> }"];
    e [label="{ <data> 17 | <ref> }"];
    
    a -> b [style=invis]
    b:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> d:data [arrowtail=dot, dir=both, tailclip=false];
    d:ref:c -> e:data [arrowtail=dot, dir=both, tailclip=false];
}

其他 node 與 pivot 比較大小 做出 left, right
其中 right 的順序會這樣是因為元素加入順序
1.99
2.37->99
3.17->37->99

digraph foo {
    node [shape=record];
    rankdir=LR;
    
    ordering=out;
    subgraph cluster_pivot {
        label="pivot"
        a [label="{ <data> 12 | <ref> }"];
    }    
    subgraph cluster_left {
        label="left"
        d [label="{ <data> 5  | <ref> }"];
    } 
    subgraph cluster_right {
        label="right"
        b [label="{ <data> 99 | <ref> }"];
        c [label="{ <data> 37 | <ref> }"];
        e [label="{ <data> 17 | <ref> }"];
    }
    
    d -> a [style=invis]
    a -> e [style=invis]
    e:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false]
    c:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false]
}

接下來對 left 與 right 作 quicksort

digraph foo {
    rankdir="LR"
    label="left"
    node [shape=record]
    d [label="{ <data> 5 | <ref> }"];
}

只有一個 node 或沒有 node 會直接 return

digraph foo {
    rankdir="LR"
    label="right"
    node [shape=record]
    subgraph cluster_pivot {
        label="pivot2"
        e [label="{ <data> 17 | <ref> }"];
    }    
    subgraph cluster_left {
        label="left2"
        x [style=invis]
    } 
    subgraph cluster_right {
        label="right2"
        b [label="{ <data> 99 | <ref> }"];
        c [label="{ <data> 37 | <ref> }"];
    }
    x -> e [style=invis]
    e -> b [style=invis]
    b:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false];
}

對 right2 作 quicksort

digraph foo {
    rankdir="LR"
    label="right2"
    node [shape=record]
    subgraph cluster_pivot {
        label="pivot3"
        b [label="{ <data> 99 | <ref> }"];
    }    
    subgraph cluster_left {
        label="left3"
        c [label="{ <data> 37 | <ref> }"];
    } 
    subgraph cluster_right {
        label="right3"
        x [style=invis]
    }
    c -> b [style=invis]
    b -> x [style=invis]
}

right2 以 left3->pivot3->right3 的方式合併

digraph foo {
    rankdir="LR"
    label="right"
    node [shape=record]
    subgraph cluster_pivot {
        label="pivot2"
        e [label="{ <data> 17 | <ref> }"];
    }    
    subgraph cluster_left {
        label="left2"
        x [style=invis]
    } 
    subgraph cluster_right {
        label="right2"
        b [label="{ <data> 99 | <ref> }"];
        c [label="{ <data> 37 | <ref> }"];
    }
    x -> e [style=invis]
    e -> c [style=invis]
    c:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false];
}

right 以 left2->pivot2->right2 的方式合併

digraph foo {
    node [shape=record];
    rankdir=LR;
    
    ordering=out;
    subgraph cluster_pivot {
        label="pivot"
        a [label="{ <data> 12 | <ref> }"];
    }    
    subgraph cluster_left {
        label="left"
        d [label="{ <data> 5  | <ref> }"];
    } 
    subgraph cluster_right {
        label="right"
        b [label="{ <data> 99 | <ref> }"];
        c [label="{ <data> 37 | <ref> }"];
        e [label="{ <data> 17 | <ref> }"];
    }
    
    d -> a [style=invis]
    a -> e [style=invis]
    e:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false]
    c:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false]
}

原本的 list 以 left->pivot->right 的方式合併

digraph foo {
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> 12 | <ref> }"];
    b [label="{ <data> 99 | <ref> }"];
    c [label="{ <data> 37 | <ref> }"];
    d [label="{ <data> 5  | <ref> }"];
    e [label="{ <data> 17 | <ref> }"];
    d:ref:c -> a:data [arrowtail=dot, dir=both, tailclip=false];
    a:ref:c -> e:data [arrowtail=dot, dir=both, tailclip=false];
    e:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false];
}

最後 sort 就完成了
## Pseudorandom number generator
測試程式使用的亂數產生是 `random()`
產生的亂數可能不會是真正的亂數
因此將 `random()` 改成有 `time.h` 輔助的 `rand()`

#include<time.h>

.
.
.

int main(int argc, char **argv) {
    size_t count = 20;

    node_t *list = NULL;
    srand(time(NULL));
    while (count--)
        list = list_make_node_t(list, rand() % 1024);

## Non-Recursive QuickSort
參考 [Optimized QuickSort](https://alienryderflex.com/quicksort/)
把其中 array 的部份換成 linked list

void quicksort_iter(node_t **list)
{
#define MAX_LEVELS 300

    int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R, swap, elements;
    elements = listSize(*list);

    beg[0] = 0;
    end[0] = elements;
    while (i >= 0) {
        L = beg[i];
        R = end[i] - 1;
        if (L < R) {
            piv = get_node_value(*list, L);
            while (L < R) {
                while (get_node_value(*list, R) >= piv && L < R)
                    R--;
                if (L < R) {
                    //arr[L++] = arr[R];
                    swap_node(L, R, list);
                    L++;
                }
                while (get_node_value(*list, L) <= piv && L < R)
                    L++;
                if (L < R)
                    //arr[R--] = arr[L];//change array to linked list
                    swap_node(L, R, list);
                    R--;
            }
            //arr[L] = piv;//change array to linked list
            beg[i + 1] = L + 1;
            end[i + 1] = end[i];
            end[i++] = L;
            if (end[i] - beg[i] > end[i - 1] - beg[i - 1]) {
                swap = beg[i];
                beg[i] = beg[i - 1];
                beg[i - 1] = swap;
                swap = end[i];
                end[i] = end[i - 1];
                end[i - 1] = swap;
            }
        } else {
            i--;
        }
    }
}

上面有用到一些小 function
`swap_node`

void swap_node(int L, int R, node_t **list)
{
    int L_value, R_value;
    node_t *tmp = *list, *L_node, *R_node;
    
    for (int i = 0; i <= R; i++) {
        if (i == L) {
            L_value = tmp->value;
            L_node = tmp;
        }
        if (i == R) {
            R_value = tmp->value;
            R_node = tmp;
        }
        tmp = tmp->next;
    }
    L_node->value = R_value;
    R_node->value = L_value;
}

`get_node_value`

int get_node_value(node_t *n, int num)
{
    for (int i = 0; i < num; i++)
           n = n->next;
    return n->value;
}