---
# System prepended metadata

title: 2021q1 Homework1 (quiz1)
tags: [linux2021]

---

# 2021q1 Homework1 (quiz1)
contributed by < `nickchenchj` >
###### tags: `linux2021`

## Prerequisite
* [2021q1 第 1 週測驗題 - HackMD](https://hackmd.io/@sysprog/linux2021-quiz1)

## Linked list
From [Wikipedia](https://en.wikipedia.org/wiki/Linked_list):
> In computer science, a _linked list_ is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

### Singly linked list (SLL)
The structure of SLL is represented as:
```c
typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;
```
and the schematic representation of SLL is:
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    head [
        shape=plaintext
        fontcolor=blue
    ]
    node1 [
        label="{ <value> value | <next> }"
    ]
    node2 [
        label="{ <value> value | <next> }"
    ]
    NULL [shape=plaintext]
    
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```

### Linked list operations
* **`list_add_node_t`**: insert a new node at the **beginning** of the list
* **`list_concat`**: concatenate two lists
* **`quicksort`**: sort the list in ascending order using quicksort algorithm
* **`list_display`**: print all of the nodes in the list

### Quicksort on singly linked list
The implementation of quicksort is shown below:
```cpp=
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;
}

static 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;
}
```

To understand how this implementation works, we need to look into the concept of quicksort. Excerpted from [Wikipedia](https://en.wikipedia.org/wiki/Quicksort):
> Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. ... The sub-arrays are then sorted **recursively**.

Assume there are five nodes in the list pointed to by `list`, and the values are `30`, `50`, `10`, `40`, and `20`. The schematic diagram looks like:

```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    list [
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    
    node1 [
        label="{ <value> 30 | <next> }"
    ]
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    node3 [
        label="{ <value> 10 | <next> }"
    ]
    node4 [
        label="{ <value> 40 | <next> }"
    ]
    node5 [
        label="{ <value> 20 | <next> }"
    ]
    NULL [shape=plaintext]
    
    list -> head [color=red]
    head -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> node4 [tailclip=false]
    node4:next:c -> node5 [tailclip=false]
    node5:next:c -> NULL [tailclip=false]
}
```

#### Choosing a pivot
In this implementation, the first node in the list is selected as the pivot, which is the node with the value of `30` in this list. And the list without pivot is pointed to by `p`.
* **pivot**
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    pivot [
        label="pivot"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node1 [
        label="{ <value> 30 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]

    pivot -> node1 [color=blue]
    node1:next:c -> NULL [tailclip=false]
}
```

* **remaining nodes**
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    p [
        label="p"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    node3 [
        label="{ <value> 10 | <next> }"
    ]
    node4 [
        label="{ <value> 40 | <next> }"
    ]
    node5 [
        label="{ <value> 20 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]

    p -> node2 [color=blue]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> node4 [tailclip=false]
    node4:next:c -> node5 [tailclip=false]
    node5:next:c -> NULL [tailclip=false]
}
```

#### Partitioning the remaining nodes
After the pivot is selected, the remaining nodes will be partitioned into two sublists (`left` and `right`), according to the value of the pivot. Since `list_add_node_t()` inserts the node at the beginning of the linked list, the resulting sublists will be in reverse order (original: `10`→`20`; reversed: `20`→`10`).

* **left**: nodes less than the pivot
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    left [
        label="left"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node1 [
        label="{ <value> 20 | <next> }"
    ]
    node2 [
        label="{ <value> 10 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    left -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```

* **right**: nodes greater than the pivot
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    right [
        label="right"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node1 [
        label="{ <value> 40 | <next> }"
    ]
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    right -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```

#### Sorting the sublists recursively
The sublists are sorted recursively after partitioning (partitioning stops when no sublist can be found from a list). The following are the new `pivot`, new `left` (`left'`) and new `right` (`right'`), which are extracted from the original `left`. Note that sorting `right` will not be discussed because it has the same behavior as sorting `left`.
* **pivot**: the first node in `left`
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    pivot [
        label="pivot"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node1 [
        label="{ <value> 20 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]

    pivot -> node1 [color=blue]
    node1:next:c -> NULL [tailclip=false]
}
```

* **left'**: nodes less than the pivot
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    left [
        label="left'"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node1 [
        label="{ <value> 10 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    left -> node1 [color=blue]
    node1:next:c -> NULL [tailclip=false]
}
```

* **right'**: nodes greater than the pivot
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    right [
        label="right'"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]

    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    right -> NULL [color=blue]
}
```

#### Concatenating the sublists
After the sublists are sorted in ascending order, the sorted sublists and the pivot are then concatenated.
1. Concatenate the sublists of `left`:
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    result [
        label="left"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    left [
        label="left'"
        shape=plaintext
        fontcolor=skyblue
    ]
    pivot [
        label="pivot"
        shape=plaintext
        fontcolor=skyblue
    ]
    
    node1 [
        label="{ <value> 10 | <next> }"
    ]
    node2 [
        label="{ <value> 20 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    result -> node1 [color=blue]
    pivot -> node2:s [color=skyblue]
    left -> node1:s [color=skyblue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```
2. Concatenate the sublists of `right`:
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    result [
        label="right"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    pivot [
        label="pivot"
        shape=plaintext
        fontcolor=skyblue
    ]
    right [
        label="right'"
        shape=plaintext
        fontcolor=skyblue
    ]
    
    node1 [
        label="{ <value> 40 | <next> }"
    ]
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    result -> node1 [color=blue]
    pivot -> node1:s [color=skyblue]
    right -> node2:s [color=skyblue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```
3. Concatenate `left`, `pivot`, and `right`:
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    result [
        label="result"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    left [
        label="left"
        shape=plaintext
        fontcolor=skyblue
    ]
    pivot [
        label="pivot"
        shape=plaintext
        fontcolor=skyblue
    ]
    right [
        label="right"
        shape=plaintext
        fontcolor=skyblue
    ]
    
    node1 [
        label="{ <value> 10 | <next> }"
    ]
    node2 [
        label="{ <value> 20 | <next> }"
    ]
    node3 [
        label="{ <value> 30 | <next> }"
    ]
    node4 [
        label="{ <value> 40 | <next> }"
    ]
    node5 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    result -> node1 [color=blue]
    left -> node1:s [color=skyblue]
    pivot -> node3:n [color=skyblue]
    right -> node4:s [color=skyblue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> node4 [tailclip=false]
    node4:next:c -> node5 [tailclip=false]
    node5:next:c -> NULL [tailclip=false]
}
```

4. The whole list is now sorted in ascending order.

## Pseudorandom number generator
### Seed vs. no seed
In the previous version of the code, the program always generated the same sequence of numbers. That is, the number generator is time-independent and predictable. To know why this happened, let's view the original code:
```cpp=
int main(int argc, char **argv) {
    size_t count = 20;

    node_t *list = NULL;
    while (count--)
        list = list_make_node_t(list, random() % 1024);
    ...
}
```
The [random](https://linux.die.net/man/3/random) function uses a hidden state to generate the next number. Setting the seed modifies the initial state. However, the program above called the random function without setting the seed. According to the [man page](https://en.wikipedia.org/wiki/Man_page):
> If no seed value is provided, the random() function is automatically seeded with a value of 1.

Every time the program executes, the random function is seeded with a value of 1, therefore, the program always generates the same sequence of numbers.

If we want to generate different sequences depending on the time for each execution of the program, set the seed with the value of the current time using the [srandom](https://linux.die.net/man/3/srandom) function:
```diff=
int main(int argc, char **argv) {
+   srandom(time(NULL));
    size_t count = 20;

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

The generated sequence are now time-dependent, and they are as follows:
* output 1
```shell 
NOT IN ORDER : 969 179 290 420 687 375 33 785 568 40 96 833 661 783 141 416 391 487 539 571 
    IN ORDER : 33 40 96 141 179 290 375 391 416 420 487 539 568 571 661 687 783 785 833 969 
```
* output 2
```shell 
NOT IN ORDER : 104 892 351 676 796 207 463 468 729 389 804 785 70 829 749 483 773 922 555 999 
    IN ORDER : 70 104 207 351 389 463 468 483 555 676 729 749 773 785 796 804 829 892 922 999 
```
* output 3
```shell 
NOT IN ORDER : 928 1007 1006 571 303 701 738 559 993 140 18 724 955 987 914 427 794 875 192 238 
    IN ORDER : 18 140 192 238 303 427 559 571 701 724 738 794 875 914 928 955 987 993 1006 1007 
```

## Non-recursive quicksort on SLL
> reference: [Optimized QuickSort — C Implementation (Non-Recursive)
](https://alienryderflex.com/quicksort/)
### Synopsis
```cpp 
void quicksort_non_recursive(node_t **list);
```

### Description
The `quicksort_non_recursive` function has two arrays of `node_t *`. The two arrays are named `begin` and `end`, and they are used to store the address of the beginning and ending node in each sublist, respectively. Initially, `begin[0]` points to the first node in the list, and `end[0]` points to the end of the list, `NULL`. We reuse the example list used in [Quicksort on singly linked list](#Quicksort-on-singly-linked-list):

```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    list [
        shape=plaintext
        fontcolor=red
    ]
    head [
        shape=plaintext
        fontcolor=blue
    ]
    begin [
        label="begin[0]"
        shape=plaintext
        fontcolor=blue
    ]
    end [
        label="end[0]"
        shape=plaintext
        fontcolor=blue
    ]
    
    node1 [
        label="{ <value> 30 | <next> }"
    ]
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    node3 [
        label="{ <value> 10 | <next> }"
    ]
    node4 [
        label="{ <value> 40 | <next> }"
    ]
    node5 [
        label="{ <value> 20 | <next> }"
    ]
    NULL [shape=plaintext]
    
    list -> head [color=red]
    head -> node1 [color=blue]
    begin -> node1:n [color=blue]
    end -> NULL:n [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> node4 [tailclip=false]
    node4:next:c -> node5 [tailclip=false]
    node5:next:c -> NULL [tailclip=false]
}
```

Similar to conventional quicksort on SLL, the `quicksort_non_recursive` function selects the first node in the list, `begin[i]`, as the pivot. Then, the function splits the list into two sublists, which are `left` and `right`. Every node with value greater than that of the pivot is inserted into `right`; otherwise, the node is inserted into `left`.

* **pivot**
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    pivot [
        label="pivot"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    begin [
        label="begin[0]"
        shape=plaintext
        fontcolor=blue
    ]
    
    node1 [
        label="{ <value> 30 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]

    pivot -> node1 [color=blue]
    begin -> node1:s [color=blue]
    node1:next:c -> NULL [tailclip=false]
}
```

* **left**: nodes less than the pivot
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    left [
        label="left"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node1 [
        label="{ <value> 20 | <next> }"
    ]
    node2 [
        label="{ <value> 10 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    left -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```

* **right**: nodes greater than the pivot
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    right [
        label="right"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    
    node1 [
        label="{ <value> 40 | <next> }"
    ]
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    end [
        label="end[0]"
        shape=plaintext
    ]
    
    right -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> end [tailclip=false]
}
```

Concatenate `left`, `pivot`, and `right` after splitting the list. Then, mark the beginning and ending node of both sublists, `left` and `right`, with `begin` and `end`, respectively. The addresses stored in `begin` and `end` are shown as follows:
* `begin[i]`: the beginning node in `left`
* `end[i]`: the ending node in `left`
* `begin[i + 1]`: the beginning node in `right`
* `end[i + 1]`: the ending node in `right`

```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]
    
    result [
        label="result"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    left [
        label="left"
        shape=plaintext
        fontcolor=skyblue
    ]
    pivot [
        label="pivot"
        shape=plaintext
        fontcolor=skyblue
    ]
    right [
        label="right"
        shape=plaintext
        fontcolor=skyblue
    ]
    begin1 [
        label="begin[0]"
        shape=plaintext
        fontcolor=blue
    ]
    begin2 [
        label="begin[1]"
        shape=plaintext
        fontcolor=blue
    ]
    end1 [
        label="end[0]"
        shape=plaintext
        fontcolor=blue
    ]
    end2 [
        label="end[1]"
        shape=plaintext
        fontcolor=blue
    ]
    
    node1 [
        label="{ <value> 20 | <next> }"
    ]
    node2 [
        label="{ <value> 10 | <next> }"
    ]
    node3 [
        label="{ <value> 30 | <next> }"
    ]
    node4 [
        label="{ <value> 40 | <next> }"
    ]
    node5 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    result -> node1 [color=blue]
    left -> node1:s [color=skyblue]
    pivot -> node3:s [color=skyblue]
    right -> node4:s [color=skyblue]
    begin1 -> node1:n [color=blue]
    end1 -> node3:n [color=blue]
    begin2 -> node4:n [color=blue]
    end2 -> NULL:n [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> node4 [tailclip=false]
    node4:next:c -> node5 [tailclip=false]
    node5:next:c -> NULL [tailclip=false]
}
```

If the length of `right` is greater than 1, increment the level index `i` and sort `right` first; otherwise, sort `left`. The length of `right` is greater than 1 in this example, so we increment `i` and sort `right` first:

* **`i == 1`**:
```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    pivot [
        label="pivot"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    begin [
        label="begin[1]"
        shape=plaintext
        fontcolor=blue
    ]
    end [
        label="end[1]"
        shape=plaintext
        fontcolor=blue
    ]

    node1 [
        label="{ <value> 40 | <next> }"
    ]
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    pivot ->node1 [color=blue]
    begin -> node1:n [color=blue]
    end -> NULL:n [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```

The following list is the new `right` after partitioning and concatenation:

```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    result [
        label="result"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    left [
        shape=plaintext
        fontcolor=skyblue
    ]
    pivot [
        shape=plaintext
        fontcolor=skyblue
    ]
    right [
        shape=plaintext
        fontcolor=skyblue
    ]
    begin1 [
        label="begin[1], end[1]"
        shape=plaintext
        fontcolor=blue
    ]
    begin2 [
        label="begin[2]"
        shape=plaintext
        fontcolor=blue
    ]
    end2 [
        label="end[2]"
        shape=plaintext
        fontcolor=blue
    ]

    node1 [
        label="{ <value> 40 | <next> }"
    ]
    node2 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    NULL1 [
        label="NULL"
        shape=plaintext
    ]
    
    result -> node1 [color=blue]
    left -> NULL1 [color=skyblue]
    pivot ->node1:s [color=skyblue]
    right -> node2:s [color=skyblue]
    begin1 -> node1:n [color=blue]
    begin2 -> node2:n [color=blue]
    end2 -> NULL:n [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> NULL [tailclip=false]
}
```

Note that `left` is considered as the unsorted part of the list. If the length of the unsorted part, `left`, is less than 2, link the node on the left hand side of `left` to `left` and decrement the level index `i`. Repeat this step until the length is greater than or equal to 2.

As illustrated in the graph above, the length of `right` is 1 (less than 2), therefore, sort `left`. Since `left` is empty, skip the sorting step and link `end[0]` to `begin[1]`. The result is shown as follows:

```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    begin1 [
        label="begin[0]"
        shape=box
        style="filled,dashed"
        fontcolor=blue
        fillcolor=yellow
    ]
    begin2 [
        label="begin[1], end[1]"
        shape=plaintext
        fontcolor=blue
    ]
    end1 [
        label="end[0]"
        shape=plaintext
        fontcolor=blue
    ]
    
    node1 [
        label="{ <value> 20 | <next> }"
    ]
    node2 [
        label="{ <value> 10 | <next> }"
    ]
    node3 [
        label="{ <value> 30 | <next> }"
    ]
    node4 [
        label="{ <value> 40 | <next> }"
    ]
    node5 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    begin1 -> node1 [color=blue]
    end1 -> node3:n [color=blue]
    begin2 -> node4:s [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> node4 [tailclip=false color=red]
    node4:next:c -> node5 [tailclip=false]
    node5:next:c -> NULL [tailclip=false]
}
```
###### Note: The red arrow is the newly created link that connects `end[0]` to `begin[1]`.

Because the length of the unsorted part, `begin[0]` (inclusive) to `end[0]` (exclusive), is 2, sort this part using the same steps introduced above.

The sorting process completes when the number of nodes between `begin[0]` (inclusive) and `end[0]` (exclusive) is less than 2. Finally, change the head of the list to `begin[0]` and end the function. The sorted list is as follows:

```graphviz
digraph SLL {
    rankdir=LR
    node [shape=record]

    list [
        shape=plaintext
        fontcolor=red
    ]
    begin [
        label="begin[0], end[1]"
        shape=plaintext
        fontcolor=blue
    ]
    
    node1 [
        label="{ <value> 10 | <next> }"
    ]
    node2 [
        label="{ <value> 20 | <next> }"
    ]
    node3 [
        label="{ <value> 30 | <next> }"
    ]
    node4 [
        label="{ <value> 40 | <next> }"
    ]
    node5 [
        label="{ <value> 50 | <next> }"
    ]
    NULL [
        label="NULL"
        shape=plaintext
    ]
    
    list -> begin [color=red]
    begin -> node1 [color=blue]
    node1:next:c -> node2 [tailclip=false]
    node2:next:c -> node3 [tailclip=false]
    node3:next:c -> node4 [tailclip=false]
    node4:next:c -> node5 [tailclip=false]
    node5:next:c -> NULL [tailclip=false]
}
```

The implementation of non-recursive quicksort on SLL is shown below:
```cpp=
static void quicksort_non_recursive(node_t **list)
{
#define MAX_LEVELS 1000
    node_t *begin[MAX_LEVELS], *end[MAX_LEVELS];

    begin[0] = *list;
    end[0] = NULL;
    int i = 0;

    while (i >= 0 && i < MAX_LEVELS - 1) {
        /* Initializes pivot, left, and right */
        node_t *pivot = begin[i];
        int value = pivot->value;
        node_t *ptr = pivot->next;
        pivot->next = NULL;
        node_t *left = NULL, *right = end[i];

        /* Splits the current list into two sublists */
        while (ptr != end[i]) {
           node_t *n = ptr;
           ptr = ptr->next;
           list_add_node_t(n->value > value ? &right : &left, n);
        }

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

        /* Resets the beginning and ending nodes of the sublists.
         * left: i; right: i + 1 */
        begin[i] = result;
        begin[i + 1] = right; /* right == pivot->next */
        end[i + 1] = end[i];
        end[i] = pivot;

        /* `right` has only 0-1 nodes */
        if (begin[i + 1] != end[i + 1] && begin[i + 1]->next != end[i + 1]) {
            i++;
        } else {
            /* `left` has only 0-1 nodes */
            while (begin[i] == end[i] || begin[i]->next == end[i]) {
                if (i > 0)
                    /* Concatenates the list on the LHS and `left` */
                    end[i - 1]->next = begin[i];
                else {
                    *list = begin[i];
                    return;
                }
                i--;
            }
        }
    }
    fprintf(stderr, "sorting failed, max level reached\n");
    exit(EXIT_FAILURE);
#undef MAX_LEVELS
}
```

Note: In the worst-case scenario, which means that the list is already sorted in ascending order, the `quicksort_non_recursive` function can only sort lists of length less than `MAX_LEVELS`.

### Recursive quicksort vs. non-recursive quicksort
#### Benchmark
