2024q1 Homework2 (quiz1+2)

contributed by < otteryc >

第一周測驗

第一題

本題中，透過 begin 以及 end 兩個堆疊，來實作迭代的 quicksort 。前述兩個堆疊的大小是待排序鏈結串列元素個數的兩倍，並且分別用來儲存尚未完成排序的鏈結串列的起始位置以及結束位置。

 while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = it->next;
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = list_tail(&left);
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&right);

            left = right = NULL;
            i += 2;
        } else {
            // Saving the element to returning linked-list, omitted here.
        }
    }

每次迭代的過程中，分別從兩個堆疊中取出起始以及結束的指標，並且以起始指標作為 pivot ，接著走訪兩個指標中間的每個節點，並分治為兩個子連結串列，最後將其與 pivot 一同推入兩個堆疊之中。
值得注意的是，本實作的空間複雜度是

$O(2n+2)$，而且 begin 以及 end 都儲存於記憶體的 stack 區段，有造成 stack-based buffer overflow 的疑慮。

第二週測驗

?