2021q1 Homework (quiz1)

contributed by <roger90810>

完成測驗並解釋
引入 Pseudorandom number generator
Optimized Quciksort (Non-Recursive)
改寫 linux-list 的 quick sort 範例
研讀 A Comparative Study of Linked List Sorting Algorithms

main 分析

程式一開始先建立有 20 個 node 的 list
這些 node 的值為 random 產生

size_t count = 20;
node_t *list = NULL;
while (count--)
    list = list_make_node_t(list, random() % 1024);

在給的 code 中沒有 list_make_node_t 這個 function，經過分析後得出此 function 為加入新的 node 到目前 list 的前面，並回傳目前 list 的第一個 node，因此自己加入 list_make_node_t :

static node_t *list_make_node_t(node_t *list, int val) 
{
  node_t *node = (node_t *)malloc(sizeof(node_t));
  node->value = val;
  node->next = list;
  return node;
}

此時已經可以透過 list_display 印出整個 list 的值

NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359

NULL, EXIT_FAILURE, EXIT_SUCCESS macro
在 C11 規格書中的 7.22 General utilities <stdlib.h> 提到 :

The macros defined are NULL (described in 7.19);
EXIT_FAILURE
and
EXIT_SUCCESS
which expand to integer constant expressions that can be used as the argument to the
exit function to return unsuccessful or successful termination status

所以必須 #include <stdlib.h>
而 NULL 的定義則是在 stddef.h 中，但 stdlib.h 中已經有 #include <stddef.h>，所以可以不用自己再 include 一次

實際去查看 stdlib.h 中發現這兩個 macro 其實就是定義一個常數，和一般寫的 return 0; 是一樣意思

/* We define these the same for all machines.
   Changes from this to the outside world should be done in `_exit'.  */
#define	EXIT_FAILURE	1	/* Failing exit status.  */
#define	EXIT_SUCCESS	0	/* Successful exit status.  */

實作 free_list

在給的程式碼中，有用到 list_free，但並沒有實作
因此自己加入這段程式碼，並透過 valgrind 測試確實 free 掉 list

static void list_free(node_t **list)
{
    node_t *p = *list;
    while (p) {
        node_t *n = p;
        p = p->next;
        free(n);
    }
}

valgrind 輸出結果:

==1064== Memcheck, a memory error detector
==1064== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1064== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==1064== Command: ./list
==1064==
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
    IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
==1064==
==1064== HEAP SUMMARY:
==1064==     in use at exit: 0 bytes in 0 blocks
==1064==   total heap usage: 21 allocs, 21 frees, 1,344 bytes allocated
==1064==
==1064== All heap blocks were freed -- no leaks are possible
==1064==
==1064== For lists of detected and suppressed errors, rerun with: -s
==1064== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

quicksort 分析

quicksort 使用 divide and conquer 的方法，先將問題拆成多個子問題，解決子問題後，再將這些子問題合併，因此朝這個方向去思考，程式應該可以分成兩個部分

divide
combine

由以下程式碼可得知 pivot 的選擇為 list 的第一個元素

node_t *pivot = *list
int value = pivot->value;

1. divide

由以下程式碼推斷，這裡是要將原 list 拆成 left, pivot, right 三個 list
首先利用 pivot->next = NULL 即可拆出只有 pivot 這個節點的 list
接著在 while loop 中，透過和 pivot 比較，可以將所有剩下的 node 拆成兩個 list
- list left，此 list 中所有節點的值皆小於等於 pivot 的值
- list right，此 list 中所有節點的值皆大於 pivot 的值

node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL;
node_t *right = NULL;
// while loop ...
quicksort(&left);
quicksort(&right);

while loop 的部分，就是如何拆出 left 和 right 這兩個 list

由程式碼分析出，n 和 p 的用途為走訪 list
n 表示當前的節點，p 表示下一個要進行比較的節點
list_add_node_t 的用途為插入一個節點到 list 的前面，因此可推出這邊是要將節點 n 插入到 list AAA 或 list BBB 的前面
觀察程式碼也發現，n 要插到哪裡是由 n->value > value? ，也就是和 pivot 的值比較來決定，因此可得出
- 若 n 的值大於 pivot 的值，則需要插入到 list right，並且 n 成為 list right 的第一個節點
- 若 n 的值小於等於 pivot 的值，則需要插入到 list left，並且 n 成為 list right 的第一個節點

while(p) {
    node_t *n = p;
    p = p->next;
    list_add_node_t(n->value > value? AAA : BBB, n);
}

所以得出

AAA = (e) &right
BBB = (c) &left

2. Combine

將 list 拆開 sort 後，需要將結果合併回來
因此需要合併 left, pivot, right 三個 list

首先分析 list_concat 的作法

先猜測此函式的用途為在一個 list 後面接上另一個 list
只需要將 list 中最後一個節點的 next 接到另一個 list 中第一個節點即可
這裡的做法 :
- left 一開始指到 list1 的第一個節點，並透過 while loop，最終會指到 list1 最後一個節點的 next，此時為 NULL
- 將 NULL 改成 list2 的第一個節點，就會使 list1 的最後一個節點接到 list2 的第一個節點，即可完成 concat

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

所以得出

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

分析完 list_concat 的方法後，即可得知只要依序將 left, pivot, right 接起來，就可以得到遞增順序排序的 list

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

所以得出

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

經過程式碼驗證，可得到正確結果

完整程式碼:

list.h

#ifndef LIST_H_INCLUDE
#define LIST_H_INCLUDE

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct __node {
    int value;
    struct __node *next;
} node_t;

// add node to the front of the list
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);  // LLL
    *left = 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 ? &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;
}
#endif

list.c

#include "list.h"

static bool list_is_ordered(node_t *list)
{
    bool first = true;

    int value;
    while (list) {
        if (first) {
            value = list->value;
            first = false;
        } else {
            if (list->value < value)
                return false;
            value = list->value;
        }
        list = list->next;
    }
    return true;
}

static void list_display(node_t *list)
{
    printf("%s IN ORDER : ", list_is_ordered(list) ? "   " : "NOT");
    while (list) {
        printf("%d ", list->value);
        list = list->next;
    }
    printf("\n");
}
static node_t *list_make_node_t(node_t *list, int val)
{
    node_t *node = (node_t *) malloc(sizeof(node_t));
    node->value = val;
    node->next = list;
    return node;
}

static void list_free(node_t **list)
{
    node_t *p = *list;
    while (p) {
        node_t *n = p;
        p = p->next;
        free(n);
    }
}
int main(int argc, char **argv)
{
    size_t count = 20;

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

    list_display(list);
    quicksort(&list);
    list_display(list);

    if (!list_is_ordered(list))
        return EXIT_FAILURE;

    list_free(&list);
    return EXIT_SUCCESS;
}

輸出結果:

NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
    IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016

2021q1 Homework (quiz1)

main 分析

quicksort 分析

1. divide

2. Combine

Read more

Aquila Boot Linux

OS Homework1

2021q1 Homework1 (lab0)