# 2021q1 Homework1 (quiz1)

contributed by < `kksweet8845` >

## Test 1

1.

 LLL = left = &((*left)->next)

The first problem is the `LLL` is located in `list_concat` function.
Now we can consider the `list_concat` function, shown as following.

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

We can know that this function is aimed to concatenate two list.
The `left` is a pointer of pointer of node_t, that is, this is a address of pointer of node_t of `next`.

digraph G {
     node [shape=record];
     rankdir=LR
     
     l_head[label="{<data>0|<ref>next}"];
     l0[label="{<data>1|<ref>next}"];
     l1[label="{<data>2|<ref>next}"];
     l2[label="{<data>3|<ref>next}"];
     left[label="left", shape="plaintext"];
     lNULL[label="NULL", shape="plaintext"]
     r0[label="{<data>0|<ref>next}"];
     r1[label="{<data>1|<ref>next}"]
     r2[label="{<data>2|<ref>next}"];
     right[label="right", shape="plaintext"]
     rNULL[label="NULL", shape="plaintext"]
     
     
     right -> r0:data
     r0:ref:to -> r1:data
     r1:ref:to -> r2:data
     r2:ref:to -> rNULL
     left -> l_head:ref
     l_head:ref:to -> l0:data
     l0:ref:to -> l1:data
     l1:ref:to -> l2:data
     l2:ref:to -> lNULL
     
}

In line 4, `*left = right` will concatenate left and right shown as following.

digraph G {
     node [shape=record];
     rankdir=LR
     
     l_head[label="{<data>0|<ref>next}"];
     l0[label="{<data>1|<ref>next}"];
     l1[label="{<data>2|<ref>next}"];
     l2[label="{<data>3|<ref>next}"];
     left[label="left", shape="plaintext"];
     r0[label="{<data>0|<ref>next}"];
     r1[label="{<data>1|<ref>next}"]
     r2[label="{<data>2|<ref>next}"];
     right[label="right", shape="plaintext"]
     rNULL[label="NULL", shape="plaintext"]
     
     
     right -> r0:data
     r0:ref:to -> r1:data
     r1:ref:to -> r2:data
     r2:ref:to -> rNULL
     left -> l_head:ref
     l_head:ref:to -> l0:data
     l0:ref:to -> l1:data
     l1:ref:to -> l2:data
     l2:ref:to -> r0:data
     
}

In order to realize the goal shown above, we need to transfer the `left` pointer to the `next` of right most node. That is,

digraph G {
     node [shape=record];
     rankdir=LR
     
     l_head[label="{<data>0|<ref>next}"];
     l0[label="{<data>1|<ref>next}"];
     l1[label="{<data>2|<ref>next}"];
     l2[label="{<data>3|<ref>next}"];
     left[label="left", shape="plaintext"];
     // r0[label="{<data>0|<ref>next}"];
     // r1[label="{<data>1|<ref>next}"]
     // r2[label="{<data>2|<ref>next}"];
     // right[label="right", shape="plaintext"]
     // rNULL[label="NULL", shape="plaintext"]
     lNULL[label="NULL", shape="plaintext"]
     
     
     // right -> r0:data
     // r0:ref:to -> r1:data
     // r1:ref:to -> r2:data
     // r2:ref:to -> rNULL
     l_head:ref:to -> l0:data
     l0:ref:to -> l1:data
     l1:ref:to -> l2:data
     l2:ref:to -> lNULL
     left -> l2:ref
     
}

That is, `left = &((*left)->next)`, which is a operation to transfer to the next node of `next` pointer.

2.

 AAA = &right 
 BBB = &left

In line 15, This line of code performs the quick sort algorithm, which will transfer the node which `value` worse than the node called `pivot` to the left and greater than `pivot` to the 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 ? AAA : BBB, n);
    }

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

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

digraph G {
    node [shape="record"]
    rankdir=LR
    pivot[label="{<val>23|pivot}"]
    right[label="{<val>50| greater than pivot}"]
    left[label="{<val>12| worse than pivot}"]
    
    left -> pivot -> right
}

`n->value > value ? AAA : BBB`, `AAA` is address of `left` pointer and `BBB` is address of `right` pinter.

4.

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

Finally, we can concatenate the `left` list and `right` list. And don't forget the pivot node, which is `left` < `pivot` < `right`.

## Principle
This program implements the quick sort algorithm. The core of this program is to split recursively.

digraph G {
    rankdir=LR
    node[shape="record"]
    pivot[label="{4|pivot}", color="Red"]
    1->2->0->3->pivot->8->5->7->6
}

Then cut the list ending in the left of pivot and cut the list starting from the right of pivot.

digraph G {
    rankdir=LR
    node[shape="record"]
    left[label="left", shape="plaintext"]
    right[label="right", shape="plaintext"]
    pivot[label="{4|pivot}"]
    
    left -> 1 -> 2 -> 0 -> 3
    right -> 8 -> 5 -> 7 -> 6
}

Then keep split the left and right list with same mechanism, left and right list will be order eventually.

digraph G {
    rankdir=LR
    node[shape="record"]
    left[label="left", shape="plaintext"]
    right[label="right", shape="plaintext"]
    pivot[label="{4|pivot}"]
    
    left -> 0 -> 1 -> 2 -> 3
    right -> 5 -> 6 -> 7 -> 8
}

Finally, concatenate the right, left and pivot node.

digraph G {
    rankdir=LR
    node[shape="record"]
    pivot[label="{4|pivot}"]
    0->1->2->3->pivot->5->6->7->8
}