# 2024q1 Homework2 (quiz1+2)

contributed by <`EisEisHet`>

## Quiz 1
> [Link to Quiz 1](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-1")
> TODO LIST :
> Extension Questions:

> Explain how the above code works, propose improvement plans, and implement them.
> Override the above code using the Linux core-style List API, and propose a quicksort implementation for linked columns that avoids worst-case scenarios, and design a test program for performance evaluation.
### Test 1

The quicksort algorithm implemented in quiz 1 uses a non-recursive (iterative) approach and implements a linked list instead of an array. To simulate recursion, a stack method is implemented.

Consider the struct node_t:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

Each node in the linked list contains a value of type `long`, two pointers `*left` and `*right` pointing to the left and right nodes from the current node (children nodes), and a pointer `*next` pointing to the next node. If we put it visually:

digraph "queue"{
    rankdir = "LR"
    subgraph "cluster node1"{
        node1_1[shape = record, label = "next"]
        node1_2[shape = record, label = "value"]
        node1_3[shape = record, label = "{<left> left | <right>             right}"]
    }
    subgraph "cluster node2"{
        node2_1[shape = record, label = next]
        node2_2[shape = record, label = value]
        node2_3[shape = record, label = "{<left> left | <right>             right}"]
    
    }
    subgraph "cluster node3"{
        node3_1[shape = record, label = next]
        node3_2[shape = record, label = value]
        node3_3[shape = record, label = "{<left> left | <right>             right}"]
    
    }
    
    node1_1 -> node2_1
    node2_1 -> node3_1
}

### Related Linked List functions

Consider the following functions for linked lists:
#### list_add()

void list_add(node_t **list, node_t *node){
    node->next = *list;
    *list = node;  
}

This function works by adding the node to the beginning of a linked list. This is done by assigning the `next` pointer of the passing `*node` variable to the current head of the list `*list`, and then updating the head of the list to the new `node`.

#### list_tail()

node_t list_tail(node_t **left){
    while((*left) && (*left)->next){
        left = &((*left)->next);
    }
    return left;
}

This function takes the indirect pointer `**left` as a parameter to start from the head of the list. The while loop will continue iterating through the list from the head as long as the current node `*left` is not NULL and the next node is not NULL.
* While iterating, if the list is non-empty, the `left`variable will be constantly updated until the loop terminates, where `left` will contain the last node of the list.
* If the list is empty or NULL, the function would immediately return `left` or the list itself.

#### list_length()

int list_length(node_t **left){
    int count = 0;
    while(*left){
        ++count;
        left = &((*left)->next);
    }
    return count;
}

This function passes in the indirect pointer `**left` as a parameter, which represents the head, and it checks whether the current node is not NULL in a while loop. If it is not NULL, then `count` will be incremented by 1, and the current node `left`is assigned to be the `next` pointer of the current node. This repeats until `*left = null` where it will then return the `count`.

#### list_construct()

node_t *list_construct(node_t *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->next = list;
    node->value = n;
    return node;
}

This function is used to construct a node and add it to the beginning of the list. It first allocates memory of size `node_t`to a single node, `node`will then be assigned a value `n` and have its `next`pointer point to the `list`.

#### list_free()

void list_free(node_t **list)
{
    node_t *node = (*list)->next;
    while (*list) {
        free(*list);
        *list = node;
        if (node)
            node = node->next;
    }
}

This function works by accessing every single node from the list and freeing every single node of its memory. The while loop constantly checks if `*list`is not NULL, and frees the next node from the current node.

#### Non-recursive Quicksort implementation

Using the above linked list functions, we can implement a non-recursive quicksort algorithm.

void quick_sort(node_t **list){
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
        
            while (p) {
                node_t *n = p;
                p = p->next;
                list_add(n->value > value ? &right : &left, n);
            }
            
            begin[i] = left;
            end[i] = list_tail(&begin[i]);
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&begin[i + 2]);
            

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

1. We assign the first and last entry of `list` to the first entry of the pointer arrays `*begin` and `*end` respectively. The pivot variable `p` will begin from the head of `list`. Keep in mind that `begin` and `end` both act as the stack to keep track of sublists being partitioned.

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

2. This while loop acts as the partitioner of the linked list. It iterates through every single node in the linked list and checks if the value of node `n` is more or less than the value of the pivot `value`. If `n` is greater than the pivot, then `n`will be added to the `right` sublist. Otherwise, it will be added to the `left` sublist.

begin[i] = left;
end[i] = list_tail(&begin[i]);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&begin[i + 2]);

3. `begin[i]` and `end[i]` are then assigned the pointers to the start and end of the `left` sublist. Similarly, `begin[i+2]` and `end[i+2]` are assigned the start and end of the `right` sublist. `begin[i+1]` and `end[i+1]` represents the partition point, thus they are assigned the value of `pivot`.

4. After the sublists are updated, then index`i` will be incremented by 2 to move to the next level of the stack for the next iteration, and the process repeats. However, if the sublist `L` only has one element (`L == R`), then it is added to the list `result`. Index `i`is then decremented to move to the parent level of the stack.
5. After the partitioning and sorting process is complete, the head of the sorted list `result` will be assigned to the original list pointer `list`, which means successfully updating it to the sorted list.
### Test 2
#### Timsort

Timsort is a type of sorting sorting algorithm that specializes in sorting arrays that have partially sorted subsequences, which often occur with real life data.

### Timsort