對 Linked List 進行氣泡排序

contributed by < FATESAIKOU >

tags: Algorithm

原始程式碼: LLBubble

前情提要

本題是jserv老師出給我補考的第一題，當下看到其實覺得沒什麼困難，於是就寫了一個簡單版本。結果立刻遭到打臉，發現自己考慮真的太少了，也因此展開了後續的探索…

程式目的

題目希望能夠撰寫一份程式碼，實現 linked list 的bubble sort，並且包含以下限制：

• 僅能更動 next 指標指向，而不搬動內容。
• 需能處理有循環的 linked list 的排序。

節點原型宣告

typedef struct __node {
    int val;
    struct __node *next;
} Node;

程式實作

實作上使用 C 語言 (依循C99 標準) 撰寫，其中包含測試以及執行部份的程式碼，以下僅取出核心演算法的部份程式碼進行探討，更詳細請見專案連結。

使用演算法

本程式使用泡沫排序來對 linked list 進行排序，並且使用 Floyd's Algorithm進行迴圈偵測與長度計算。

程式碼簡介

首先擷取計算 linked list 長度的程式碼: findLen (cycle detection):

bool findLen(Node *head, int* mu, int* lambda) {
    if (head == NULL || head->next == NULL) {
        *mu = (head != NULL) ? 1 : 0;
        *lambda = 0;
        return false;
    } else {
        Node *t = head->next;
        Node *h = head->next->next;
        bool has_cycle = false;
        int tmu = 1;
        int tlambda = 0;
        
        // check the linked list has loop or not.
        do {
            ++tmu;
            t = t->next;

            if (h != NULL && h->next != NULL) {
                h = h->next->next;
            } else {
                h = NULL;
            }

            if (t == h && t != NULL) {
                has_cycle = true;
            }
        } while(t != h);

        if (has_cycle) {
            // find mu
            tmu = 0;
            t = head;
            while (t != h) {
                t = t->next;
                h = h->next;
                ++tmu;
            }

            // find lambda
            do {
                t = t->next;
                ++tlambda;
            } while (t != h);
        }

        *mu = tmu;
        *lambda = tlambda;
        return has_cycle;
    }
}

除了一些特殊狀況的處理，可以發現其主邏輯就是先確定是否包含迴圈之後才接著計算迴圈長度(lambda)以及非迴圈長度(mu)，其中其判斷是否包含迴圈以及迴圈長度等，皆是利用Floyd's Cycle Detection Algorithm 這套演算法。這個演算法特點便是十分節省記憶體，僅需要兩個指標 (tortoise & hare) 就可以完成偵測。

演算法使用兩個指標，烏龜一次走一步、兔子則是走兩步，兩者速度不同，當 linked list 中存在迴圈時則兔子總有一天會追上烏龜，並且烏龜與兔子所行走得距離差必定是迴圈長度的倍數。

至於起點與迴圈起點的距離，只要利用距離差為整數倍的特性推導即可。
假設兩者在距離起點

$x$ 的點

$P_x$ 相遇，因此點必在迴圈上，可得知

$x$ 為迴圈長度

$\lambda$ 的整數倍，接著令

$b$ 為迴圈起始點

$P_{\mu }$ 與

$P_x$ 的距離，令

$a$ 為

$P_{\mu }$ 前的某一點與

$P_{\mu }$ 的距離，使得

$a+b=\lambda$，其中

$P_{\mu }$ 與起點的距離為

$\mu$，以此可以推導出:

$x=n\lambda ,n\in {\mathbb{Z}}^{+}$

$\mu =x-b=(n-1)\lambda +(\lambda -b)=(n-1)\lambda +a$
其中迴圈起始點與起點的距離為:

$(n-1)\lambda +a$
而

$x$ 與迴圈起始點的距離為:

$\lambda -b=a$
以下示意圖：

由此可以發現，若想知道迴圈起始點

$P_{\mu }$，僅須將烏龜推回起點，兔子不動，接著兩者皆以一次一步的方式前進，兩者必定會在迴圈起始點相遇。最後再讓兔子繞一圈便可以取得迴圈長度

$\lambda$，至此算是初步了解此演算法。

接著是排序時使用的主邏輯: sort

void sort(Node **head) {
    int mu, lambda, total_len;
    bool has_cycle = findLen(*head, &mu, &lambda);
    total_len = mu + lambda;
                        
    int now_len = total_len;
    while (now_len) {
        *head = floatUp(*head, now_len);
        --now_len;
    }

    if (has_cycle)
        link(*head, total_len - 1, mu - 1);
}

可發現主邏輯包含三個部份：

• 迴圈偵測與長度計算
• 排序
• 連結

第一及第二部份還可以理解，但為何在排序結束後還會需要特別連結尾端與迴圈起始點呢？其實是因為 linked list 經過這個排序之後，節點順序會遭到調換，導致迴圈起點位置遭到更換，如下圖：

雖然可以透過將所有節點的關係建表，或者是在排序時針對迴圈起始點做特殊處理來解決，但以上兩者不管在實做複雜度上或者是執行的空間時間複雜度上都較差，因此採用最後重新進行連結的作法。

接著是 Bubble Sort 的實際排序的部份，也是 sort 中用到的floatUp:

Node *floatUp(Node *head, int len) {
    if (len == 1) {
        return head;
    } else {
        Node *a = head;
        Node *b = head->next;
    
        if (a->val > b->val) {
            Node *t = b->next;
            a->next = t;
            b->next = floatUp(a, len - 1);
            return b;
        } else {
            a->next = floatUp(b, len - 1);
            return a;
        }
    }
}

可以發現上面其實就是泡沫排序中泡泡向上浮出的過程，其只更動指標指向進行排序。

測試

測試方法

本程式測試主要分兩部分，連結測試Link Test、以及Sort Test，前者用於測試 Link List 連結狀況於排序前後是否相同，後者用於測試排序本身是否正確。

測試實作

測試時首先會產生一個數值陣列，接著將其轉換為 linked List，接著排序後進行，排序結果測試：

• Sort Test

bool validate(int *nums, int nums_len, Node *head, int ll_len) {
    if (nums_len != ll_len)
        return false;
    
    Node *cur = head;
    int i = 0;
    while (i < nums_len && cur != NULL) {
        if (nums[i] != cur->val) {        
            return false;
        } else {
            ++i;
            cur = cur->next;
        }
    }
}

可以發現在測試中因為 linked list 可能出現迴圈因此特別針對長度先行一次判斷，接著才對數值進行比對。

接著是便是對排序後迴圈的位置進行測試，這裡採用的方法是直接再對排序結果做一次 findLen，取得排序後 linked list 得到

${\mu }_2$(mu2) 以及

${\lambda }_2$(lambda2)，並且與排序前的 mu、lambda 分別進行比較即可。

• Link Test

linkValidate(Node *before_sort, Node *after_sort) {
    int mu, lambda, mu2, lambda2;
    
    findLen(before_sort, &mu, &lambda);
    findLen(after_sort, &mu2, &lambda2);
    
    return (mu == mu2 && lambda == lambda2); 
}

測試結果

其中 Len 為 linked list 長度，LoopAt 為迴圈起點(由 0 開始編號)，Loop? 則是表示是否有被偵測出迴圈，MU 與 Lambda 則對應迴圈起始點與起點距離以及迴圈長度，link test 為排序前後連結位置測試，最後 sort test 就是排序結果本身的正確性。

問題討論

為何 linked list 出現迴圈卻依然要排序？

其實在於 linux 作業系統當中，其資源便是以環狀 Linked List 的方式紀錄與管理，並且環狀 Linked List 相較於沒有環的，更不容易出現指標指向非法區段(即使執行結果錯誤)的狀況，並且不論從那一個節點開始找尋，皆能找到迴圈上所有的節點。

採用長度作為排序邊界的原因。

由於 Linked List 上可能存在迴圈，因此不能單純利用 NULL 來作為中止條件判斷，因此剩下的就只剩下紀錄：

• 結尾節點
• Linked List長度
  這兩者，以作為排序的邊界。

但實際上前者在實作時因為其必須隨時維護結尾紀錄造成：

• 需要多個判斷式維護結尾紀錄，效能低下。
• 需要更多介面傳遞結尾紀錄，甚至使用全域/環境變數，難以維護。
• 多執行緒時容易造成 race condition。

因此在此我採用 Linked List 的長度作為排序邊界。

修改指標指向，而非修改內容的優點？

現實狀況下，我們無法保證一個 Linked List 節點所儲存的資訊就像這個範例一樣只是個可更改的數字，若其中包含更大的數據量，抑或是節點數據本身不允許修改(確保安全性)，那麼比起搬動資料，更動指標指向會是更好的作法。

效能問題

由上面可以看到，在本程式是採用遞迴方式來實現 Bubble Sort 的排序過程，於此還有不少的改善空間，先寫到這裡，待後續補充。

心得

剛開始真的以為就只是個 Bubble Sort，結果一寫之下才發現這好像跟自己了解的 Bubble Sort 不太一樣，實在慚愧。這次真的學了不少，話說我的作業阿！！！！

感謝

• jserv 老師

參考資料

• Floyd's Cycle Detection Algorithm
• Bubble Sort(Wikipedia)