owned this note
owned this note
Published
Linked with GitHub
# 2021q1 Homework1 (quiz1)
contributed by ?
contributed by < `ilkclord` >
## Function analyze
* **list_add_node**
```clike
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.
```graphviz
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]
```graphviz
digraph G{
node[shape = box];
add_Node->List;
List->NULL ;
rankdir = LR;
}
```
* **list_concat**
```clike
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.
```graphviz
digraph G{
node[shape = box];
left->right;
rankdir = LR;
}
```
* **quicksort**
```clike
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 .
```graphviz
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.
```clike
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
```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**
```clike
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**
```clike
typedef struct node{
struct node *next;
struct node *pre;
int data ;
}n;
```
We add **node** ***pre** to implement the movement of R .
* **is_ordered**
```clike
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**
```clike
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 .