quit sort 非遞迴版程式步驟詳解

介紹

根據作業測驗 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);//末端節點位址

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

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;時為例

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);
}

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

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;

單步執行後面程式過程

當 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移動到下個節點
...

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

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;

下一步執行 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--;
    	}

因為 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--;
    	}

因為 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 節點

執行完 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--;
    	}

因為 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 節點

執行完 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--;
    	}

因為 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 節點

執行完 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;時

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鍊結：

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

left鍊結：

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

pivot:

節點2

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;

回到 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 串列中，變成

總結

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
才能方便調閱每個子串列

介紹

step 0

step 1

step 2.

step3.

單步執行後面程式過程

當 i=2 時

step1

step2

step3

當 i=4 時

step1

回到 i=3 時

step1

回到 i=2 時

step1

回到 i=1 時

step1

回到 i=0 時

step1

step2

step3

回到 i=2 時

step1

總結

Read more

2025q1 Homework1 (lab0)

Linux環境下 使用VS code debugging C設定步驟

2025q1 Homework1 (ideas)

2024q1 Homework2 (quiz1+2)

Linux環境下使用VS code debugging C設定步驟