Try   HackMD

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) 非遞迴快速排序法。在這個算法中,我們使用 LR 來記錄待排序部分的起始和結束位置。首先,我們將 L 設置為 pivot,然後通過 np 遍歷後面的節點。將小於 pivot->value 的節點放入 left,將大於 pivot->value 的節點放入 right。這些節點以後進先出(LIFO)的方式被存入,以相反的順序記錄著節點。以 3, 1, 2, 4, 5 做舉例







%0



pivot

pivot



3

3



pivot->3





L

L



L->3





R

R



5

5



R->5





1

1



3->1





2

2



1->2





4

4



2->4





4->5





p

p



p->1












%0



left

left



2

2



left->2





right

right



5

5



right->5





pivot

pivot



3

3



pivot->3





1

1



2->1





4

4



5->4












%0



begin[i]

begin[i]



2

2



begin[i]->2





begin[i+1]

begin[i+1]



3

3



begin[i+1]->3





begin[i+2]

begin[i+2]



5

5



begin[i+2]->5





end[i]

end[i]



1

1



end[i]->1





end[i+1]

end[i+1]



end[i+1]->3





end[i+2]

end[i+2]



4

4



end[i+2]->4





2->1





5->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 中。







%0



L

L



3

3



L->3





R

R



R->3





L 不等於 R 時,我們仍然可以將其分成 leftright 兩部分進行操作。







%0



L

L



5

5



L->5





R

R



4

4



R->4





5->4