# Week2 linked list bubble sort
contributed by <`ian910297`>
## 問題描述
對一個 Singly linked list 做 bubble sort
* 不能改變 value
* 只能改變 next 的指標

Data Structure 如下

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

## bubble sort - 無考慮 cycle
一開始，我以為只需要針對頭尾特別討論，以下為程式碼

void sort(Node **HEAD) {
    Node *cur, *tmp, *prev;
    Node *TAIL = NULL;
    
    While(*HEAD!=NULL && (*HEAD)->next!=TAIL) {
        cur = *HEAD;
        while(cur->next!=TAIL) {
            if(cur->val > cur->next->val) {
                // HEAD
                if(cur==*HEAD) {
                    *HEAD = cur->next;
                } else {
                    prev->next = cur->next;
                }
                
                // swap
                tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = cur;
                
                
                // whether is TAIL or not
                if(cur->next != TAIL) {
                    TAIL = cur;
                    break;
                }
                
                // next loop
                prev = tmp;
            } else {
                // whether is TAIL or not
                if(cur->next->next == TAIL) {
                    TAIL = cur->next;
                    break;
                }
                
                // next loop
                prev = cur;
                cur = cur->next;
            }
        }
    }
}

## Cycle Finding
在老師提醒下，發現 singly linked list 仍可能會有 cycle 產生，也就是 circular linked list ，我使用[龜兔賽跑(Floyd's algorithm)](http://www.csie.ntnu.edu.tw/~u91029/Function.html#4)來偵測是否有 cycle 產生

有三種狀態需要做討論

圖(1) cycle 在中間、圖(2) 頭尾相連、圖(3)為尾尾相連
* $a$ 為起始點
* $b$ 為連接點
* $c$ 為龜兔相遇位置

我們需要求得三點位置，才能進行處理
假設 $\overline{ac}$ 距離為 $X$ ，這代表 tortoise 走了 $X$ 步，那麼 hare 走了 $2X$ 步， $X$ 數值為多少並不重要，他只代表要花多少時間兩點才會相遇，不影響求出 $\mu , \lambda$
接下來要分成三個步驟來處理
* step1: tortoise 速度為每次一步，hare 為每次兩步，兩者同時從起點 $a$ 出發，相遇時可以得到點 $c$。如果是圖(2)的狀況，在第一步結束就求完三點了
* step2: 兩點分別從點 $a$ 、 $c$ 出發，速度皆為一次一步，相遇時可以得到點 $b$。因為 $\overline{ac}$ 長度為 $X$，那麼 $cycle$ $c$ 長度也為 $X$，相遇在點 $b$ 時，所走的距離剛好都是 $X - \overline{bc}$
* step3: 從點 $b$ 出發，速度為一次一步，再次回到點 $b$ 可以得到 cycle 的長度

## cycle finding
如果只需要判斷是否為 circular linked list，那麼只要執行 step1 的部分，是很簡單、快速。
除了計算 $\mu , \lambda$ ，還需要記錄整個串列的長度，若不記錄，會影響到之後 bubble sort 的實作。

Node* move(Node *cur) {
    if(cur!=NULL) {
        retunr cur->next;
    } else {
        return NULL;
    }
}

bool cycle_finding(Node *HEAD, Node **TAIL, int *length, int *mu, int *lambda)
{
    // lambda is length
    // mu is the meet node's index
    Node *tortoise = HEAD;
    Node *hare = HEAD;

    // get meet point
    tortoise = move(tortoise);
    hare = move(move(hare));
    while(hare!=NULL && tortoise!=hare) {
        tortoise = move(tortoise);
        hare = move(move(hare));
    }

    // not loop
    if(hare==NULL) {
        *TAIL = NULL;
        *length = 0;
        tortoise = HEAD;
        while(tortoise!=NULL && (tortoise=move(tortoise))) {
            (*length)++;
        }
        return false;
    }

    // get mu
    *mu = 0;
    tortoise = HEAD;
    while(tortoise!=hare) {
        (*mu)++;
        tortoise = tortoise->next;
        hare = hare->next;
    }

    // get lambda
    *lambda = 1;
    tortoise = move(tortoise);
    *TAIL = tortoise;
    while(tortoise!=hare) {
        *TAIL = tortoise;
        (*lambda)++;
        tortoise = move(tortoise);
    }
    *length = *mu + *lambda;

    return true;
}

## bubble sort - 加入 cycle_finding
原本以為只要完成 cycle_finding ，得到 $\mu , \lambda$ 之後就離完成作業不遠，但實際實作之後，才發現要考慮的狀況比預想的複雜。

以下為處理 circular linked list 遇到的難題
* 要討論的狀況很多，只要交換牽扯到 $\mu$ ，都需要特別再將尾巴的鏈結重新指向
* 當交換發生在結尾時
* $\mu$ 是 $HEAD$
* $\mu$ 是 $TAIL$
* 當交換發生在頭時
* $\mu$ 是 $1$
* 一般交換
* $cur \to next$ 是 $\mu$
* $cur$ 是 $\mu$
* 不知如何判定是否到結尾，若採用之前的使用 pointer 當作結尾的方法來判定，點 $\mu$ 也代表 $TAIL$ ，若使用 pointer 就無法判定是否是第一次經過點 $mu$，還是已經到結尾

void sort(Node **HEAD)
{
    Node *cur, *prev, *TAIL;
    int i, j;
    int length = 0;
    int mu = -1;
    int lambda = -1;
    bool has_cycle = cycle_finding(*HEAD, &TAIL, &length, &mu, &lambda);

    for(i=0; i<length-1; i++) {
        cur = *HEAD;
        prev = *HEAD;

        for(j=0; j<length-i-1; j++) {
            if(cur->val > cur->next->val) {
                if(cur->next==TAIL) {// for cycle
                    if(mu==0) {// link to HEAD
                        prev->next = cur->next;
                        cur->next = *HEAD;
                    } else if(cur->next==cur->next->next) {// link to self
                        prev->next = cur->next;
                        cur->next = cur;
                    } else {
                        prev->next = cur->next;
                        cur->next = prev->next->next;
                    }

                    prev->next->next = cur;
                    TAIL = cur;
                    prev = prev->next;
                } else if(cur==*HEAD) {
                    *HEAD = cur->next;

                    if(mu==1) {
                        cur->next = (*HEAD)->next;
                        (*HEAD)->next = cur;
                        TAIL->next = cur;
                    } else {
                        cur->next = (*HEAD)->next;
                        (*HEAD)->next = cur;
                    }

                    prev = *HEAD;
                } else {
                    prev->next = cur->next;
                    cur->next = prev->next->next;
                    prev->next->next = cur;

                    if(j+1==mu) {
                        TAIL->next = cur;
                    } else if(j==mu) {
                        TAIL->next = prev->next;
                    }

                    prev = prev->next;
                }
            } else {
                prev = cur;
                cur = cur->next;
            }
        }
    }
}

## 最終優化
仍使用 length 計算結尾，且若是 circular linked list ，我們只需在排序完成時，重新把 $TAIL$ 指向點 $mu$ 即可

void sort(Node **HEAD)
{
    Node *cur, *prev, *TAIL;
    int i, j;
    int length = 0;
    int mu = -1;
    int lambda = -1;
    bool has_cycle = cycle_finding(*HEAD, &TAIL, &length, &mu, &lambda);

    for(i=0; i<length-1; i++) {
        cur = *HEAD;
        for(j=0; j<length-i-1; j++) {
            if(cur->val > cur->next->val) {
                if(cur==*HEAD) {
                    *HEAD = cur->next;
                    cur->next = (*HEAD)->next;
                    (*HEAD)->next = cur;
                } else {
                    prev->next = cur->next;
                    cur->next = prev->next->next;
                    prev->next->next = cur;
                        
                    prev = prev->next;
                }
            } else {
                prev = cur;
                cur = cur->next;
            }
                                     
            if(j+1==length-1) {
                TAIL = cur;
            }
        }
    }
 
    if(has_cycle) {
        i = 0;
        cur = *HEAD;
        while(i++<mu) {
            cur = cur->next;
        }
        
        TAIL->next = cur;
    }
}

## 問題討論
### 以數學證明 Floyd's Algorithm
:::info

:::

###

## 測試
目前還沒有完成測試的程式，先以FATESAIKOU同學提供的Utils產生測資作初步的驗證

## 心得
原本在補考寫的程式碼，回家實做之後發現是完全錯誤，少了編譯器輔助，我發現我根本不能保證我程式碼的可執行性。