前言
本問題出自於 jserv - Linux 核心設計講座 第一周 linked list 和非連續記憶體操作 底下題目一的延伸題目
本篇記錄 bubble sort 在 circular doubly linked list 上的實作。
node 結構
struct node {
int data;
struct node *next, *prev;
};本題的 linked list 屬於 circular doubly linked list，因此 swap 時需要額外處理 prev 指標，還要考慮循環結構帶來的邊界問題。
Bubble sort
void bubble_sort(int *arr, const int length)
{
for(int i = 0; i < length-1; i++) {
int flag = 0;
for(int j = 0; j < length-i-1; j++) {
if(arr[j] > arr[j+1]) {
int t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
flag = 1;
}
}
if(!flag) break;
}
}在實作 linked list 版本之前，先看一下一般 array 版本的實現。bubble sort 本身邏輯容易理解，這裡比較大的挑戰是需要先實作一個 swap_node 來交換兩個 node。
swap_node
void swap_node(struct node *n1, struct node *n2) {
n1->prev->next = n2;
n2->prev = n1->prev;
n1->next = n2->next;
n2->next->prev = n1;
n1->prev = n2;
n2->next = n1;
}因為採用 doubly linked list，swap 時需要額外處理 prev 指標。下面用示意圖說明 swap 的運作過程：
假設要 swap node_2 和 node_3，swap 完之後應該變成這樣：
回顧 swap function 的定義：
swap_node(node_2, node_3);傳入的是 node_2 和 node_3 的地址，node_1 和 node_4 無法直接存取。
接著一步一步來解析，先處理 node_1 和 node_3 之間的連結：
node_1->next = node_3;
node_3->prev = node_1;由於無法直接存取 node_1，要透過 node_2->prev 來表示：
node_2->prev->next = node_3;
node_3->prev = node_2->prev;
接著處理 node_2 和 node_4 之間的連結：
node_2->next = node_4;
node_4->prev = node_2;由於無法直接存取 node_4，要表示成 node_3->next：
node_2->next = node_3->next;
node_3->next->prev = node_2;處理完之後的狀態如下，最後只需要調整 node_2 和 node_3 之間的連結：
讓 node_2->prev 指向 node_3、node_3->next 指向 node_2，完成最後的交換：
node_2->prev = node_3;
node_3->next = node_2;最後完成如下
如果對指標操作還不熟悉，建議拿紙筆自己畫一遍，會清楚很多。
Bubble sort with Circular doubly linked list
void bubble_sort(struct node **head, const int length) {
if(!*head) return;
struct node *tnode; // temp
struct node *lnode = *head;
struct node *rnode = lnode->next;
for(int i = 0; i < length - 1; i++) {
int flag = 0;
for(int j = 0; j < length - i - 1; j++) {
if(lnode->data > rnode->data) {
swap_node(lnode, rnode);
tnode = rnode;
rnode = lnode;
lnode = tnode;
flag = 1;
}
lnode = lnode->next;
rnode = rnode->next;
}
for(int j = 0; j < i+1; j++)
lnode = lnode->next;
rnode = lnode->next;
if(!flag) break;
}
*head = lnode;
}接著說明 bubble sort 在 circular doubly linked list 上的實現。根據 array 版本的邏輯，我們需要兩個指標指向要比較的相鄰節點：
struct node *lnode;
struct node *rnode;整體邏輯與一般 bubble sort 相同，但因為資料結構是 circular doubly linked list，有幾個細節需要注意：
if(lnode->data > rnode->data) {
swap_node(lnode, rnode);
tnode = rnode;
rnode = lnode;
lnode = tnode;
}繼續用剛才的例子，假設要交換 node_2 和 node_3，此時 lnode 指向 node_2、rnode 指向 node_3：
交換完之後會變成
swap 完成後，為了讓後續的比較能從正確位置繼續，需要把 lnode 和 rnode 重新指向正確的節點：
tnode = rnode;
rnode = lnode;
lnode = tnode;
傳統 bubble sort 每輪比完都要從 arr[0] 重新開始。在 circular doubly linked list 中，每輪結束後需要把 lnode 重新移回起點，再讓 rnode 指向 lnode->next：
for(int j = 0; j < i+1; j++)
lnode = lnode->next;
rnode = lnode->next;完整的程式碼放在 GitHub
之後也會補上延伸題目的 merge sort。