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

## Function analyze
* **list_add_node**

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

This function takes a pointer in and change the address pointer points to , and it is an **insert_head** function.

digraph G{
    node[shape = box];
    List->NULL;
    rankdir = LR;
}

:::danger
Re-generate the diagram via Graphviz and embedded it with HackMD.
:notes: jserv
:::

> modified ~[name=ilkclord]

digraph G{
    node[shape = box];
    add_Node->List;
    List->NULL ;
    rankdir = LR;
   
}

* **list_concat**

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

The function changes the **next** in the last node in the list ,after the process the last node's **next** will connect to the right linked list.

digraph G{
    node[shape = box];
    left->right;
    rankdir = LR;
   
}

* **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 ? &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;
}

This function take the head of **list** as pivort first , and create two seperate linked list **right** and **left**,then connect them after sorting each of them.
And the concat order is **left**->**pivot**->**right** , which follows the ascending order .

digraph G{
    node[shape = box];
    left->pivot;
    pivot->right ;
    rankdir = LR;
   
}

## Pseudorandom number generator
We can add srand() to fix it , which it changes the start of Random number table , and we often use time as the seed of rand.

srand(time)

Furthermore , the random number can easily generate by shifting and adding . For example we can define a rule that given a number we can generate next number by shift and add it to the left , and when it is >10 , which means overflow .We add the oveflow part to the next one .
**Example**
Original state : 123456789
9 + 8 = 17 : 123456879
7 + 8 = 15 : 123457579
..........
Second state : 986282579

Code in python

    # a represent the number 123456789
    for i in range( 0 , len(a)) :
        a[i] = a[i] + a2[i]
        if(a[i] > 9 and (i + 1) < len(a)) :
            a[i +1] = int((a[i + 1] +(a[i] - a[i] % 10) / 10) % 10)
        elif(a[i]  > 9 and (i +1) == len(a)) :
            a[0] = int((a[0] +(a[i] - a[i] % 10) / 10) % 10)
        a[i] = a[i] % 10

## Quick Sort Without Recursive
* **quick_sort**

void quick_sort(n * list , n * tail){
    int pivot = list->data ;
    n * L = list;
    while(L != NULL){
        display(list);
        n * R = tail;
        while(&(*L) != &(*R)){
            while(R->data > pivot) R = R->pre ;
            fake_swap(L , R);
            while(L->data < pivot) L = L->next;
            fake_swap(L , R);
        }
        L->data = pivot ;
        L = is_order(list);
        if(L == NULL)
            return ;
        else
           pivot = L->data;
    }
}

refrerence https://alienryderflex.com/quicksort/

By his design ,we implement his design . There are some fuction added to complete this program.
* **node_struct**

typedef struct node{
    struct node *next;
    struct node *pre;
    int data ;

}n;

We add **node** ***pre** to implement the movement of R .
* **is_ordered**

n *  is_order(n * root){
    while(root->next != NULL){
        if(root->data - root->next->data > 0)
          return root;
        root = root->next ;
    }
    return NULL ;
}

This function return the first node that isn't in order ,and NULL if it is well order. We have to do this because we can't guard that the left and right elements are in order . (Maybe we can do it by for-loop and size , but that seems like recursive)

* **fake_swap**

void  fake_swap(n * a , n * b){
    int tmp = a->data;
    a->data = b->data;
    b->data = tmp ;
}

This funtion swaps two node's data .I called it fake_swap because it doesn't swap the node actually, but take the nodes as an array and let the data flows .