changed a year ago  
Published Linked with GitHub

介紹

根據作業 測驗 1 介紹的 qsort 演算法原理介紹

此處提到的方法是以 swap 為主體，
利用 L 與 R 去紀錄需交換的數量，
再用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍。

假定下方是起始的陣列內容。

採取 head 作為 pivot，
並且
L 會從左邊開始掃，紀錄有多少值小於 pivot，
R 從右邊開始，紀錄有多少值大於 pivot。

step 0

在 void quick_sort(node_t **list) 中會用到下列變數

  • *begin[max_level] 和 *end[max_level] ：當成堆疊，用來紀錄

    1. *list 的頭節點，尾端節點
    2. pivot 節點
    3. *left 串列的頭端和尾端節點
    4. *right 串列的頭端和尾端節點

  • R 變數：會從右邊開始掃 *list 串列

  • L 變數：會從左邊開始掃 *list 串列
    在 L 掃 *list 串列過程中，會用到
    *left 串列：用來紀錄有多少節點值小於 pivot，
    *right 串列：用來紀錄有多少節點值大於 pivot。

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];// begin 和 end 陣列是用來存節點位址
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;//頭節點位址
    end[0] = list_tail(list);//末端節點位址

digraph {
    
    a[label="NULL", shape=box]
    b[label="NULL", shape=box]
    node [shape=box]
    graph [rankdir = "LR"];
    4 -> 1 -> 3 -> 5 -> 2 -> 7;
    node [shape=plaintext];
    pivot -> 4;
    L -> 4;
    rank=same {4 pivot L};
    R -> 7;
    rank=same {7 R};
    list->4;
	left->a;
    right->b;	
}

陣列的 Graphviz 畫法參考
Graphviz draw array data structure

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "" -> "begin[i]"  [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0> begin[0] = *list; | <f1> | <f2>  | <f3>  | <f4> | <f5> ", color=white];
    begin [label="<f0> 4 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];

    { rank=same; ""; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers:f0 -> begin:f0;

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    ""->"end[i]"  [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0> end[0] = list_tail(list); | <f1> | <f2>  | <f3>  | <f4> | <f5> ", color=white];
    end [label="<f0> 7 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];

    { rank=same; ""; pointers }
    { rank=same; "end[i]"; end }

    edge [color=blue];
    pointers:f0 -> end:f0;

}

step 1

從*begin[max_level] 取出一個 index 矩陣資料begin[i] 當成 L 節點
從*end[max_level] 取出一個 index 矩陣資料end[i] 當成 R 節點

while (i >= 0) {

	node_t *L = begin[i], *R = end[i];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
	if (L != R) {
		node_t *pivot = L;//選定 L 為 pivot
		value = pivot->value;//記下 pivot 節點的 value
		node_t *p = pivot->next;//*p  為pivot的下一個節點位址
		//因為*p已經先備份好  pivot的下一個節點了
		pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...

當 i=0;時為例

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "L" ->"begin[i]" [color=white];

    pointers [label="4", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 4 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];

    { rank=same; "L"; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers-> begin:f0[label="  *L = begin[0]",dir=back];

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "R" ->"end[i]" [color=white];

    pointers [label="7", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 7 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];

    { rank=same; "R"; pointers }
    { rank=same; "end[i]"; begin }

    edge [color=blue];
    pointers-> begin:f0[label="  *R = end[0]",dir=back];

}

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    1 -> 3 -> 5 -> 2 -> 7;
    node [shape=plaintext, fontsize=18];
    
    "P"->1  [color=white];   
  node [shape=box]
    pivot[label="pivot", shape=box,color=white];
    pivot->4[color=white];
    
    rank=same{4 1};
    4->1;
}

step 2.

比較的節點n value(n->value ) 和 pivot 節點的 value (value )
list_add(n->value > value ? &right : &left, n);

  • n->value 值大於 pivot ，則放在 right 串列（代表 pivot的右邊）
  • 若 n->value 值大於 pivot 為否，代表 n->value 值小於 pivot ，則放在 left 串列（代表 pivot 的左邊）
while (p) {
	node_t *n = p;
	p = p->next;//CCCC
	list_add(n->value > value ? &right : &left, n);
}

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    1 -> 3 -> 5 -> 2 -> 7;
    node [shape=plaintext, fontsize=18];
    
    "P"->1  [color=white];   
  node [shape=box]
    pivot[label="pivot", shape=box,color=white];
    pivot->4[color=white];
    
    rank=same{pivot 4 7};
    4->7;
}

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;//因為新節點的 next 位址都是指向 list head，所以串鍊結時是倒著串
    *list = node_t;
}

因此經過 list_add(n->value > value ? &right : &left, n); 後

right鍊結：

  • 頭端節點為 7
  • 尾端節點為 5

left鍊結：

  • 頭端節點為 2
  • 尾端節點為 1
digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    1->3->2[dir=back];
    5->7[dir=back];
    node [shape=plaintext, fontsize=18];
    "left"->1[color=white];
    "right"->5[color=white]; 

}

step3.

比較結束，將 begin[i] 與 end[i] 儲存 left 的頭與尾，
begin[i+1] 與 end[i+1] 儲存 pivot ，
begin[i+2] 與 end[i+2] 儲存 right 的頭與尾，
將 i 設為 i + 2 ，也就是堆疊的最上層

	if (L != R) {
		...
		begin[i] = left;//將 begin[i] 設為 left 的頭
		end[i] = list_tail(&left) ;//DDDD  end[i] 設為 left 的尾
		begin[i + 1] = pivot;//begin[i+1] 與 end[i+1] 設為 pivot ， 
		end[i + 1] = pivot;
		begin[i + 2] = right;//begin[i+2] 與 end[i+2] 設為 right 的頭與尾，將 i 設為 i + 2 
													//，也就是堆疊的最上層，
		end[i + 2] =list_tail(&right) ;//EEEE

		left = right = NULL;
		i += 2;
	} else {
		if (L)
			list_add(&result, L);
		i--;
	}

當 i=0;時為例

	begin[0] = left;//將 begin[i] 設為 left 的頭
	end[0] = list_tail(&left) ;//DDDD  end[i] 設為 left 的尾
	begin[1] = pivot;//begin[i+1] 與 end[i+1] 設為 pivot ， 
	end[1] = pivot;
	begin[2] = right;//begin[i+2] 與 end[i+2] 設為 right 的頭與尾，將 i 設為 i + 2 
												//，也就是堆疊的最上層，
	end[2] =list_tail(&right) ;//EEEE

	left = right = NULL;
	i += 2;

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    //"end[i]" ->"begin[i]" [color=white];
    "begin[i]"->"end[i]"  [color=white];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 7 (right 頭) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (right 尾) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
       
    { rank=same; "end[i]"; end }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
 
}

單步執行後面程式過程

當 i=2 時

step1

while (i >= 0) {

	node_t *L = begin[2], *R = end[2];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
	if (L != R) {
		node_t *pivot = L;//選定 L 為 pivot
		value = pivot->value;//記下 pivot 節點的 value
		node_t *p = pivot->next;//*p  為pivot的下一個節點位址
		//因為*p已經先備份好  pivot的下一個節點了
		pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...


digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "R" ->"end[i]"[color=white];
    pointers [label="5", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (right 尾) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "R"; pointers }
    { rank=same; "end[i]"; end }

    edge [color=blue];
    pointers-> end:f2[label="  *R = end[2]",dir=back];

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "L" ->"begin[i]"[color=white];
    pointers [label="7", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 7 (right 頭) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "L"; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers-> begin:f2[label="  *L=begin[2]",dir=back];

}

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    7->5;
    node [shape=plaintext, fontsize=18];
    "L"->7  [color=white];   

}

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    rank=same{pivot 5 7};
    7->5;
    pivot[label="pivot", shape=box,color=white];
    rank=same{pivot 7};
    pivot->7[color=white];
    node [shape=plaintext, fontsize=18];
    "p"->5  [color=white];  

}

step2

while (p) {
	node_t *n = p;
	p = p->next;//CCCC
	list_add(n->value > value ? &right : &left, n);
}

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;//因為新節點的 next 位址都是指向 list head，所以串鍊結時是倒著串
    *list = node_t;
}

因此經過 list_add(n->value > value ? &right : &left, n); 後

right鍊結：

  • 頭端節點為 NULL
  • 尾端節點為 NULL

left鍊結：

  • 頭端節點為 5
  • 尾端節點為 5
digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    5;
    node [shape=plaintext, fontsize=18];
    "left"->5;
    "right"->"NULL"; 

}

step3

當 i=2;時為例

	begin[2] = left;//將 begin[i] 設為 left 的頭
	end[2] = list_tail(&left) ;//DDDD  end[i] 設為 left 的尾
	begin[3] = pivot;//begin[i+1] 與 end[i+1] 設為 pivot ， 
	end[3] = pivot;
	begin[4] = right;//begin[i+2] 與 end[i+2] 設為 right 的頭與尾，將 i 設為 i + 2 
												//，也就是堆疊的最上層，
	end[4] =list_tail(&right) ;//EEEE

	left = right = NULL;
	i += 2;

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    //"end[i]" ->"begin[i]" [color=white];
    "begin[i]"->"end[i]"  [color=white];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
       
    { rank=same; "end[i]"; end }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
 
}

下一步執行 i=4 的情況

當 i=4 時

step1

while (i >= 0) {

	node_t *L = begin[4], *R = end[4];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
	if (L != R) {
		node_t *pivot = L;//選定 L 為 pivot
		value = pivot->value;//記下 pivot 節點的 value
		node_t *p = pivot->next;//*p  為pivot的下一個節點位址
		//因為*p已經先備份好  pivot的下一個節點了
		pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
	
	} else {
            if (L)
                list_add(&result, L);
            i--;
    	}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "R" ->"end[i]"[color=white];
    pointers [label="NULL", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "R"; pointers }
    { rank=same; "end[i]"; end }

    edge [color=blue];
    pointers-> end:f4[label="  *R = end[4]",dir=back];

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "L" ->"begin[i]"[color=white];
    pointers [label="NULL", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "L"; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers-> begin:f4[label="  *L=begin[4]",dir=back];

}

因為 node_t *L = begin[4], *R = end[4]; 取到的值都是 NULL ( L==R 的條件)
所以直接跳到

	else {
		if (L) /// L 為 null 所以不用 list_add（）
		  list_add(&result, L);
		i--;
	}

執行完 i--，回到 i=3 的情況，重新執行 step1-step3 步驟

回到 i=3 時

step1

while (i >= 0) {

	node_t *L = begin[3], *R = end[3];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
	if (L != R) {
		node_t *pivot = L;//選定 L 為 pivot
		value = pivot->value;//記下 pivot 節點的 value
		node_t *p = pivot->next;//*p  為pivot的下一個節點位址
		//因為*p已經先備份好  pivot的下一個節點了
		pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
	
	} else {
            if (L)
                list_add(&result, L);
            i--;
    	}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "R" ->"end[i]"[color=white];
    pointers [label="7", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "R"; pointers }
    { rank=same; "end[i]"; end }

    edge [color=blue];
    pointers-> end:f3[label="  *R = end[3]",dir=back];

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "L" ->"begin[i]"[color=white];
    pointers [label="7", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "L"; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers-> begin:f3[label="  *L=begin[3]",dir=back];

}

因為 node_t *L = begin[3], *R = end[3]; 取到的值都是 節點7 ( L==R 的條件)
所以直接跳到

	else {
		if (L) /// L 為 節點7 所以執行 list_add（）
		  list_add(&result, L);
		i--;
	}

result 插入 L 節點

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    7;
    node [shape=plaintext, fontsize=18];
    rank=same{"result " 7};

}

執行完 i--，回到 i=2 的情況，重新執行 step1-step3 步驟

回到 i=2 時

step1

while (i >= 0) {

	node_t *L = begin[2], *R = end[2];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
	if (L != R) {
		node_t *pivot = L;//選定 L 為 pivot
		value = pivot->value;//記下 pivot 節點的 value
		node_t *p = pivot->next;//*p  為pivot的下一個節點位址
		//因為*p已經先備份好  pivot的下一個節點了
		pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
	
	} else {
            if (L)
                list_add(&result, L);
            i--;
    	}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "R" ->"end[i]"[color=white];
    pointers [label="5", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "R"; pointers }
    { rank=same; "end[i]"; end }

    edge [color=blue];
    pointers-> end:f2[label="  *R = end[2]",dir=back];

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "L" ->"begin[i]"[color=white];
    pointers [label="5", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "L"; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers-> begin:f2[label="  *L=begin[2]",dir=back];

}

因為 node_t *L = begin[2], *R = end[2]; 取到的值都是 節點5 ( L==R 的條件)
所以直接跳到

	else {
		if (L) /// L 為 節點5 所以執行 list_add（）
		  list_add(&result, L);
		i--;
	}

result 插入 L 節點

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    7->5[dir=back];
    node [shape=plaintext, fontsize=18];
    rank=same{"result" 7};

}

執行完 i--，回到 i=1 的情況，重新執行 step1-step3 步驟

回到 i=1 時

step1

while (i >= 0) {

	node_t *L = begin[1], *R = end[1];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
	if (L != R) {
		node_t *pivot = L;//選定 L 為 pivot
		value = pivot->value;//記下 pivot 節點的 value
		node_t *p = pivot->next;//*p  為pivot的下一個節點位址
		//因為*p已經先備份好  pivot的下一個節點了
		pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
	
	} else {
            if (L)
                list_add(&result, L);
            i--;
    	}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "R" ->"end[i]"[color=white];
    pointers [label="4", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "R"; pointers }
    { rank=same; "end[i]"; end }

    edge [color=blue];
    pointers-> end:f1[label="  *R = end[1]",dir=back];

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "L" ->"begin[i]"[color=white];
    pointers [label="4", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "L"; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers-> begin:f1[label="  *L=begin[1]",dir=back];

}

因為 node_t *L = begin[1], *R = end[1]; 取到的值都是 節點4 ( L==R 的條件)
所以直接跳到

	else {
		if (L) /// L 為 節點4 所以執行 list_add（）
		  list_add(&result, L);
		i--;
	}

result 插入 L 節點

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    7->5->4[dir=back];
    node [shape=plaintext, fontsize=18];
    rank=same{"result " 7};

}

執行完 i--，回到 i=1 的情況，重新執行 step1-step3 步驟

回到 i=0 時

step1

while (i >= 0) {

	node_t *L = begin[i], *R = end[i];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
	if (L != R) {
		node_t *pivot = L;//選定 L 為 pivot
		value = pivot->value;//記下 pivot 節點的 value
		node_t *p = pivot->next;//*p  為pivot的下一個節點位址
		//因為*p已經先備份好  pivot的下一個節點了
		pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...

當 i=0;時

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "R" ->"end[i]"[color=white];
    pointers [label="1", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    end [label="<f0> 1 (left 尾)  | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "R"; pointers }
    { rank=same; "end[i]"; end }

    edge [color=blue];
    pointers-> end:f0[label="  *R = end[0]",dir=back];

}

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    "L" ->"begin[i]"[color=white];
    pointers [label="2", color=black,shape=box];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    begin [label="<f0> 2 (left頭)  | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    { rank=same; "L"; pointers }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
    pointers-> begin:f0[label="  *L=begin[0]",dir=back];

}

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    2->3->1;
    node [shape=plaintext, fontsize=18];
    "L"->2  [color=white];   

}

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    2;
    node [shape=plaintext, fontsize=18];
    "pivot"->2  [color=white];   

}

step2

while (p) {
	node_t *n = p;
	p = p->next;//CCCC
	list_add(n->value > value ? &right : &left, n);
}

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    3->1;
    node [shape=plaintext, fontsize=18];
    
    "p"->3  [color=white];   
  node [shape=box]
    pivot[label="pivot", shape=box,color=white];
    pivot->2[color=white];
    
    rank=same{pivot 2 3};
    2->3;
}

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;//因為新節點的 next 位址都是指向 list head，所以串鍊結時是倒著串
    *list = node_t;
}

因此經過 list_add(n->value > value ? &right : &left, n); 後

right鍊結：

  • 頭端節點為 1
  • 尾端節點為 1

left鍊結：

  • 頭端節點為 3
  • 尾端節點為 3

pivot:

  • 節點2
digraph {

  node [shape=box]
    graph [rankdir = "LR"];
	3;	
    1;
    node [shape=plaintext, fontsize=18];
	"right"->3; 
    "left"->1;


}

step3

當 i=0;時為例

	begin[0] = left;//將 begin[0] 設為 left 的頭
	end[0] = list_tail(&left) ;//DDDD  end[0] 設為 left 的尾
	begin[1] = pivot;//begin[1] 與 end[1] 設為 pivot ， 
	end[1] = pivot;
	begin[2] = right;//begin[2] 與 end[2] 設為 right 的頭與尾，將 i 設為 i + 2 
												//，也就是堆疊的最上層，
	end[2] =list_tail(&right) ;//EEEE

	left = right = NULL;
	i += 2;

digraph {
    node [shape=plaintext, fontcolor=red, fontsize=18];
    //"end[i]" ->"begin[i]" [color=white];
    "begin[i]"->"end[i]"  [color=white];
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    
    begin [label="<f0> 1 (left頭)  | <f1> pivot 2 | <f2> 3 (right 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
    
    end [label="<f0> 1 (left 尾)  | <f1> pivot 2 | <f2> 3 (right  尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
       
    { rank=same; "end[i]"; end }
    { rank=same; "begin[i]"; begin }

    edge [color=blue];
 
}

回到 i=2 時

step1

因為

*L = begin[2]～begin[0]; 
*R = end[2]～end[0];

都是 L==R 相同節點值

	else {
		if (L) /// L 為 節點4 所以執行 list_add（）
		  list_add(&result, L);
		i--;
	}

所以都是重複執行，將 L 節點（begin[2]～begin[0]; ） 依序插入到 result 串列中，變成

digraph {

  node [shape=box]
    graph [rankdir = "LR"];
    7->5->4->3->2->1[dir=back];
    node [shape=plaintext, fontsize=18];
    rank=same{"result 頭" 1};
    rank=same{"result 尾" 7};

}

總結

  • Quick Sort 分類成兩個串列

    1. 大於 pivot 的 right 串列
    2. 小於 pivot 的 left 串列

  • 本來在 Quick Sort 遞迴版，
    只要將這兩個串列再代入 void quick_sort(node_t **list)
    就能進一步排序 right 串列，left 串列裡面的資料大小

  • 但是我們 Quick Sort 是用 "非遞迴" 寫法，
    所以得拆成兩個子陣列排序
    例如 拆成
    left 陣列 [5,7]
    right 陣列 [1,3,2]
    兩個子陣列得另外排序

  • 幸好我們是用 link list 串列寫法，
    所以不用再額外分配連續空間的子陣列空間
    left 子串列 5–>7
    right 子串列 1–>3–>2

  • 為了方便管理每個子串列
    因此用陣列 begin[] 和 end[]     來管理每個子陣列的
    head 節點，尾節點，pivot
    才能方便調閱每個子串列

Select a repo