# 2024q1 Homework2 (quiz1+2)

contributed by < `LIAO-JIAN-PENG` >

## 第一週測驗題

### 測驗一
#### shuffle

/* shuffle array, only work if n < RAND_MAX */
void shuffle(int *array, size_t n)
{
    if (n <= 0)
        return;

    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

在 rand() 函式中，它生成的隨機數的範圍是 0 到 RAND_MAX。然而，我們需要的是一個介於 i 到 n-1 之間的隨機整數。

一種方法是將 rand() 函式生成的隨機數除以 (RAND_MAX / (n - i) + 1)。這樣可以得到一個介於 0 到 (n - i) - 1 之間的隨機整數。然後，我們將這個值加上 i，這樣就可以得到介於 i 到 n-1 之間的隨機整數。添加 1 的目的是確保 (n - i) 不為 0，以避免除法計算可能導致的錯誤。

> C 語言規格書 7.22.2.1
> The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.

#### 非遞迴快速排序法
這段程式碼使用了 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 非遞迴快速排序法。在這個算法中，我們使用 `L` 和 `R` 來記錄待排序部分的起始和結束位置。首先，我們將 `L` 設置為 `pivot`，然後通過 `n` 和 `p` 遍歷後面的節點。將小於 `pivot->value` 的節點放入 `left`，將大於 `pivot->value` 的節點放入 `right`。這些節點以後進先出（LIFO）的方式被存入，以相反的順序記錄著節點。以 `3, 1, 2, 4, 5` 做舉例

digraph {
    "pivot"[shape=box]
    "L"[shape=box]
    "R"[shape=box]
    3[shape=box]
    1[shape=box]
    2[shape=box]
    4[shape=box]
    5[shape=box]
    pivot->3
    {rank=same 3 1 2 4 5}
    L->3->1->2->4->5
    R->5
    p->1
}

---

digraph {
    "left"[shape=box]
    "right"[shape=box]
    "pivot"[shape=box]
    3[shape=box]
    1[shape=box]
    2[shape=box]
    4[shape=box]
    5[shape=box]
    pivot->3
    left->2->1
    right->5->4
}

---

digraph {
    "begin[i]"[shape=box]
    "begin[i+1]"[shape=box]
    "begin[i+2]"[shape=box]
    "end[i]"[shape=box]
    "end[i+1]"[shape=box]
    "end[i+2]"[shape=box]
    3[shape=box]
    1[shape=box]
    2[shape=box]
    4[shape=box]
    5[shape=box]
    "begin[i]"->2->1
    "begin[i+1]"->3
    "begin[i+2]"->5->4
    "end[i]"->1
    "end[i+1]"->3
    "end[i+2]"->4
    
}

在這個過程中，我們使用 `begin[i]` 和 `end[i]` 來分別記錄 `left` 部分的開始和結束位置，使用 `begin[i+1]` 和 `end[i+1]` 來記錄 `pivot`，以及使用 `begin[i+2]` 和 `end[i+2]` 來記錄 `right` 部分的開始和結束位置。每次循環中 `i+=2` 表示我們下一次迭代將針對 `right` 部分進行排序。

當 `L` 等於 `R` 時，這表示我們只剩下一個節點，我們將排序結果放入 `result` 中。

digraph {
    "L"[shape=box]
    "R"[shape=box]
    3[shape=box]
    L->3
    R->3
}

當 `L` 不等於 `R` 時，我們仍然可以將其分成 `left` 和 `right` 兩部分進行操作。

digraph {
    "L"[shape=box]
    "R"[shape=box]
    5[shape=box]
    4[shape=box]
    L->5->4
    R->4
}