2021q1 Homework1 (quiz1)

contributed by < chiehen >

tags: linux2021

作業要求

• 解釋上述程式運作原理，搭配 Graphviz
  • 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
• 參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
• 請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
• 研讀 Ching-Kuang Shene (冼鏡光] 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中

解釋程式

程式為單向 linked-list 的 quicksort 實做
主要跟 quick sort 有關的函式有以下:

• list_add_node_t: 將一個 node 加入 list 開頭
• list_concat: 將兩個 list 以頭尾相接的方式連接
• quicksor: 執行 quicksort 演算法

list_concat

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

第一次迴圈完:

第二次(全部)迴圈完:

此時 left 中為指向元素(value=5)的next的指標, 透過此指標將 next 中的值改為指向 right 所指向的元素:

*left = right;

result 即為指向連接後 list 開頭的指標

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

假設有一 list:

到第 10 行結束時將如下:

迴圈中將大於 value 的 node 分到 right, 小於的分到 left,
經過第一次迴圈(line 11 - 15):

結束迴圈:

接著分別排序 right, left
第 23 行前:

第 23 行後:

第 24 行後:

list 變為指向排序完 list 的 pointer to pointer

補完程式

• list_make_node_t: 建立一個 value 為 val 的 node , 並加在 list 前端
• list_free: 釋放 list 所配置的記憶體

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

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

Random

原先 random() 將 回傳 一個介於 0 to RAND_MAX 的整數, 而根據 維基百科:

The Pseudorandom number generator(PRNG)-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values)

數列將被初始值(initial value)決定, 根據 Linux Programmer's Manual:

The srandom() function sets its argument as the seed for a new sequence
of pseudo-random integers to be returned by random(). These sequences
are repeatable by calling srandom() with the same seed value. If no
seed value is provided, the random() function is automatically seeded
with a value of 1.

因此呼叫 srandom 時設定初始值, 而為了保證初始值不同, 則將現今時間作為初始值:

srandom(time(NULL));

修改 quick sort 程式碼 避免遞迴

參考 Optimized QuickSort — C Implementation (Non-Recursive) 實做 non-resursive quick sort。
因為在文章中的資料是以 array 的方式儲存, 如果是 linked-list 在實做上需要 doubly linked list 才有辦法實現, 因此參考課程討論區以 stack 的方式實做 non-resursive quick sort。

定義 stack 結構:

typedef struct __snode {
  node_t *value; // 儲存 sorted linked-list 
  struct __snode *next; // 指向下一個 stack 元素
} snode_t;

兩個輔助函式對 stack 操作

• stack_push: 將元素推入 stack
• stack_pop: 將元素彈出 stack, 並回傳儲存的 list 指標

static void stack_push(snode_t **top, node_t *list) {
  snode_t *new = malloc(sizeof(snode_t));
  if (!new)
    return;
  new->value = list;
  new->next = *top;
  *top = new;
}

static node_t *stack_pop(snode_t **top) {
  snode_t *curr = *top;
  if (curr) {
    node_t *list = curr->value;
    *top = curr->next;
    free(curr);
    return list;
  }
  return NULL;
}

依 pivot 調整數列的部份, 沿用原先程式的方法, 分為 right, left 兩個 list。 但在調整完後, 將 right, pivot, left依序推入 stack:

if(left) stack_push(&stack, left);
stack_push(&stack, pivot);
if(right) stack_push(&stack, right);

持續將 stack 最頂端的 list 進行 Quick Sort, 如果最頂端的 list 只有一個元素, 則將此元素加到 result 前端, 當 stack 為空時, 代表 sorting 完成:

while (stack) {
    node_t *pivot = stack_pop(&stack);
    int value = pivot->value;
    node_t *p = pivot->next;
    if (!p) {
      list_add_node_t(&result, pivot);
    } else {
      // 進行 quick sort
      .....
    }
}
*list = result;

完整 non-recursive quick sort:

void optquicksort(node_t **list) {
  snode_t *stack = NULL;
  node_t *result = NULL;
  stack_push(&stack, *list);
  while (stack) {
    node_t *pivot = stack_pop(&stack);
    int value = pivot->value;
    node_t *p = pivot->next;
    if (!p) {
      list_add_node_t(&result, pivot);
    } else {

      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);
      }
      if(left) stack_push(&stack, left);
      stack_push(&stack, pivot);
      if(right) stack_push(&stack, right);
    }
  }
  *list = result;
}

如何改進上述程式碼？
jserv

改寫 linux-list 的 quick sort 範例

研讀 Ching-Kuang Shene (冼鏡光] 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms