99高中資訊科選修課程 夥伴學習教師 專業進修研習 進階程式設計--演算法 教學示例與研討 報告人 國立鳳新高級中學 林光耀 2010.10

高中資訊科課程架構 進階程式設計 (2學分) 「資訊科技概論」必修2~4學分(生活領域) 「資訊科學」選修0～6學分(非升學科目) 2學分必修：核心知識為主 4學分必修： 核心知識＋應用軟體 或/及 基礎程式設計 「資訊科學」選修0～6學分(非升學科目) 基礎程式設計 (1～2學分) 進階程式設計 (2學分) 資訊科學與應用專題 (1～4學分) 其它(可依各校課程特色開設，0～2學分)

99總綱選修科目與學分數 選修

基礎程式設計(選修1~2學分) 一、概論 二、基礎觀念 三、流程控制 四、陣列 五、模組化程式設計※ 1.程式設計簡介 2.程式設計工具 1.程式設計簡介 2.程式設計工具 2～4 二、基礎觀念 1.常數與變數 2.基本輸入輸出 3.運算式與指定敍述 4.內建函式※ 4～6 三、流程控制 1.選擇敘述 2.重複敘述 8～14 四、陣列 1.一維陣列 2.多維陣列※ 2～8 五、模組化程式設計※ 1.副程式※ 2.程式庫※ 0～6

四、演算法 進階程式設計(選修2學分) 一、模組化程式設計 二、進階資料型態 三、資料結構 1.排序演算法 2.搜尋演算法 1.副程式 2.程式庫 6～10 二、進階資料型態 1.陣列 2.資料錄 3.指標※ 8～12 三、資料結構 1.佇列 2.堆疊 3.鏈結串列 4.樹狀結構※ 5.集合※ 10～12 四、演算法 1.排序演算法 2.搜尋演算法

單元摘要 本主題旨在介紹常用的演算法，以及如何針對演算法進行效能分析。 授課重點應強調演算法垂直式邏輯思考的精神，以及循序漸進的解題流程，並搭配日常生活實例進行教學。 先備知識 1.必修科目「資訊科技概論」 2.選修科目「基礎程式設計」

課綱範圍 1.排序演算法 約 7HR 2.搜尋演算法 約 5HR 1-1 排序演算法用途 1-2 泡沫排序演算法 1-3 選擇排序演算法 1-4 快速排序演算法※ 1-5 排序演算法效能分析※ 2.搜尋演算法 2-1 搜尋演算法用途 2-2 循序搜尋演算法 2-3 二分搜尋演算法 2-4 搜尋演算法效能分析 約 7HR 約 5HR

學習目標 能分別說明各式常見排序演算法的功能，及其在程式設計中的使用時機。 能說明並比較各式排序演算法的差異。 能利用複雜度分析方法，分析各式排序演算法的效能。 能分別說明各式常見搜尋演算法的功能，及其在程式設計中的使用時機。 能說明並比較各式搜尋演算法的差異。 能利用複雜度分析方法，分析各式搜尋演算法的效能。

第一堂課：排序介紹 一、排序介紹 二、排序演算法分析 1.何謂排序(Sorting)？ 2.內部排序 VS 外部排序 1.穩定度 2.時間複雜度 VS 空間複雜度

排序(Sorting) 是指將一群資料，依照特定規則調整位置順序，使資料具有某種次序。 目的在使資料隨著特定順序排列組合。 如班級成績資料，可以使用每個學生的總成績、總平均、名次或座號順序等排列方式，將資料由大至小或是由小至大來排列。 內部排序：排序的資料量小，可以完全在記憶體內進行排序。內部排序法有：泡沫排序法、選擇排序法、快速排序法等。 外部排序：排序的資料量無法直接在記憶體內進行排序，而必須使用到輔助記憶體。外部排序法有：直接合併排序法、堆積合併排序法等。(※)

直接移動 VS 邏輯移動 「直接移動」是直接交換儲存資料的位置。 如圖示。 「邏輯移動」並不會移動資料儲存位置，僅改變指向這些資料的輔助指標的值。 如圖示。

排序穩定度 穩定排序(Stable Sort)是指資料在經過排序後，兩個相同鍵值的記錄仍然保持原來的次序。 舉例說明：如下例中，8左的原始位置本來在8右的左邊(所謂8左及8右是指相同鍵值一個在左，一個在右。)，穩定排序後8左仍應在8右的左邊，不穩定排序則有可能8左會跑到8右的右邊去。 原始資料順序： 8左 6 9 8右 7 穩定的排序： 6 7 8左 8右 9 不穩定的排序： 6 7 8右 8左 9

時間複雜度 VS 空間複雜度 時間複雜度(Time complexity)： 1.可分為最好情況(Best Case)、最壞情況(Worst Case)及 平均情況(Average Case)。 2.最好情況就是資料已完成排序。例如：原本資料已經完成 遞增(由小至大)排序，如果再進行一次遞增排序所使用的 時間複雜度就是最好情況。 3.最壞情況是指每一鍵值均須重新排列。例如：原本為遞增 排序重新排序成為遞減(由大至小)，就是最壞情況。 空間複雜度(Space complexity)： 1.指演算法在執行過程所需付出的額外記憶體空間。 2.排序法所使用到的額外空間愈少，空間複雜度就愈佳。 3.例如泡沫排序法在排序過程中僅用到一個額外空間，在所 有的排序演算法中，這樣的空間複雜度就算是最佳情況。

第二堂課：泡沫排序法介紹 1.排序原理： 泡沫排序演算法，又稱為氣泡排序法或交換排序法。是由觀察水中氣泡大小會隨著水深高度壓力變化演進而成。 泡沫排序法的比較方式是由第一個元素開始，比較2個相鄰元素大小，若大小順序有誤，則立即對調，對調後再進行下一個元素的比較。 2.教師舉例：(以五筆隨機資料，用泡沫排序法表示演算法過程。) 例題：「26,5,37,1,61」。結果：「1,5,26,37,61」。 3.學生練習：(可隨機挑選若干位同學，以座號上台操作演練。) 例題：數列「23,36,5,14,9」(隨機挑選同學座號，各班可能不同。)若經由泡沫排序法由小到大的順序排序，過程及結果為何？ 隨機挑選若干張撲克牌，由學生(可分組進行)操作泡沫排序法由小到大，互相觀察排序過程。

第三堂課：泡沫排序法程式 程式參考示例與練習：(重點解說) void Bubble_Sort(int n, int *Data) { /* N筆資料儲存於Data[0]….Data[n-1]中 */ int i, j, temp; for (i=0;i<n-1;i++) { for(j=0;j<n-i;j++) { if (Data[j+1]<Data[j]) { temp=Data[j]; Data[j]=Data[j+1]; Data[j+1]=temp; /* 交換資料 swap */ } } printf("第 %d 次排序後的結果:",i+1); ShowData(6,Data); /* 列印每次排序後的資料 */ }

第四堂課：選擇排序法介紹 1.排序原理： 2.教師舉例：(同「26,5,37,1,61」例，用選擇排序法表示過程。) 選擇排序法可使用兩種方式排序，一為在所有的資料中，當由大至小排序，則將最大值放入第一位置；若由小至大排序時，則將最大值放入位置末端。 選擇排序法分析： 1.不是穩定排序法。 2.時間複雜度為O(n2)。 3.只需一個額外的空間，所以空間複雜度為最佳。 4.適用於資料量小或有部份資料已經過排序者。 2.教師舉例：(同「26,5,37,1,61」例，用選擇排序法表示過程。) 3.學生練習：(可隨機挑選若干位同學，以座號上台操作演練。) 例題：隨機挑選同學座號，形成數列「33,17,6,24,9」，經由選擇排序法由小到大的順序排序，過程及結果為何？ 隨機挑選若干張撲克牌，由學生(可分組進行)操作選擇排序法由小到大，互相觀察排序過程。

第五堂課：選擇排序法程式 程式參考示例與練習：(重點解說) void Select_Sort(int n, int *Data) { /* N筆資料儲存於Data[0]...Data[n-1]中 */ int i,j,k,temp; for (i=0;i<n-1;i++) { k=i; /* 掃瞄n-1次 */ for(j=i+1;j<n;j++) if(Data[j]<Data[k]) k=j; /* 尋找最小鍵值資料 */ if(i!=k) /*交換資料 swap*/ {temp=Data[i]; Data[i]=Data[k];Data[k]=temp;} /* 使此次掃瞄的最小鍵值資料擺在最前面 */ printf("第 %d 次排序後的結果:",i+1); ShowData(n,Data); } }

第六堂課：快速排序法介紹 1.排序原理： 快速排序法又稱分割交換排序法，是目前公認最佳的排序法。假設有n筆記錄R1，R2，R3，…，Rn，其鍵值分別為k1，k2，k3，…，kn。快速排序法的步驟如下： (1)取K為第一筆鍵值。 (2)由左向右找出一個鍵值Ki使得Ki>K。 (3)由右向左找出一個鍵值Kj使得Kj<K。 (4)若i<j則Ki與Kj交換，並繼續步驟(2)的執行。 (5)若ij則將K與Kj交換，並以j為基準點將資料分為左右兩部份。 (6)以遞迴方式分別為左右兩半繼續分別進行排序，直至完成排序。 快速排序法分析： 1.快速排序法不是穩定排序法。 2.時間複雜度：最快及平均為O(nlog2n)，最壞為O(n2)。 3.空間複雜度：最差情況為O(n)，最佳情況為O(log2n)。 4.快速排序法是平均執行時間最快的排序法。

第六堂課：快速排序法介紹 2.教師舉例： 可利用以上過程，將左半部與右半部分別排序，形成遞迴，至於排序過程如下：

第七堂課：快速排序法程式 程式參考示例與練習：(重點解說) void q_sort(int *data,int m,int n) { int k,temp,i,j; /* 分割元素 */ if(m<n) /* 是否繼續分割 */ { i = m; /* 分割的最左 */ j = n + 1; /* 分割的最右 */ k = data[m]; /* 取第一個元素 */ do { do /* 由左往右找 */ { i++; } while(data[i]<k); do /* 由右往左找 */ { j--; } while(data[j]>k); if (i<j) /*交換資料*/ { temp=data[i]; data[i]=data[j]; data[j]=temp; } } while(i<j); temp=data[m]; data[m]=data[j]; data[j]=temp; /*交換資料*/ printf("過程輸出: "); for (i=m;i<=n;i++) /*列印過程*/ printf("%3d",data[i]); printf("\n"); q_sort(data,m,j-1); q_sort(data,j+1,n);/*快速排序遞迴呼叫*/ } }

第八堂課：搜尋介紹 一、搜尋介紹 二、常見的搜尋方法 三、循序搜尋演算法介紹 1.何謂搜尋(Search)？ 2.靜態搜尋 VS 動態搜尋 1.循序搜尋法。(適合未經排序整理的資料) 2.二元搜尋法。(適合已經排序整理的資料) 3.其他：如內插搜尋法、費氏搜尋法。(斟酌補充※) 三、循序搜尋演算法介紹 1.搜尋原理 2.效能分析

第八堂課：搜尋介紹 靜態搜尋 VS 動態搜尋 1.靜態搜尋：指在搜尋過程中，該資料不會有增加、刪除、或更新等行為。例如符號表搜尋。 2.動態搜尋：指所搜尋的資料，在搜尋過程中會經常性增加、刪除、或更新。例如B-tree搜尋。 內部搜尋 VS 外部搜尋 1.內部搜尋：資料量較小的檔案，可以直接全部載入記憶體中進行搜尋。 2.外部搜尋：資料量大的檔案，無法一次載入記憶體處理，而需使用到輔助記憶體來分次處理。

第八堂課：循序搜尋法介紹 循序搜尋法： 1.又稱為線性搜尋法，是一種最簡單的搜尋法。 2.優點是資料在搜尋之前不需要作任何的前置處理或排 序，缺點為搜尋速度較慢。 3.因此在平均狀況下，循序搜尋法搜尋一筆資料大約需 要(n+1)/2的比較次數。 循序搜尋法分析： 1.時間複雜度：如果資料沒有重覆，找到資料就可中止 搜尋的話，在最差狀況是未找到資料，需作n次比較， 時間複雜度為O(n)。 2.當資料量很大時，不適合使用循序搜尋法。但如果預 估所搜尋的資料在檔案前端則可以減少搜尋的時間。

第九堂課：循序搜尋法程式 程式參考示例與練習：(重點解說) int search(int *data, int n, int key) { /* 資料比對的部分 */ int i; for(i=0; i<n; i++) /* 循序比對資料 */ if(data[i]==key) return i; /*找到傳回第i筆*/ return n; } /* 沒找到資料 */

第十堂課：二分搜尋法介紹 二分搜尋法原理： 將已排序的資料分割成兩等份，再比較鍵值與中間值，如果鍵值小於中間值，可確定要找的資料在前半段，否則在後半部。如此分割數次直到找到或確定找不到(不存在)為止。 二分法分析： 1.時間複雜度：因為每次搜尋都會比上一次少一半的範圍， 最多約只需要比較[log2n]+1，時間複雜度為O(log2n)。 2.二分法必須事先經過排序，且資料量必須能直接在記憶體 中執行。適合用於不需增刪的靜態資料。 舉例說明： 學生練習： 隨機挑選若干張撲克牌，由學生(可分組進行)先操作排序法(演算法不拘)由小到大，再使用二分搜尋法找出指定的牌並互相觀察操作過程。

第十堂課：二分搜尋法介紹 舉例說明： 例如以下已排序數列 2、3、5、8、9、11、12、16、18 ，而所要搜尋值為11時： (1)首先跟第五個數值9比較： (2)因11＞9，故和後半部的中間值(第七個數值)12比較： (3)因11＜12，故和前半部的中間值(第六個數值)11比較： (4)因為11=11，表示搜尋完成，如果不相等則表示找不到。 9 12

第11堂課：二分搜尋法程式 程式參考示例與練習：(重點解說) int binary(int *k, int n, int key) { int u, l, m; u=n; l=0; while(u>=l) { /*資料比對的迴圈部分*/ m=(u+l)/2; if(k[m]==key) return m; else if(k[m]<key) l=m+1; else u=m-1; } return -1; }

第12堂課：搜尋法分析 一、搜尋演算法程式改進討論： 二、搜尋演算法效能分析： 三、結論： 1.循序搜尋演算法： 2.二分搜尋演算法： (1)無須事先排序。 (2)最好情形為1次。最差情形為n次(找不到)。 (3)與其資料項數成正比，時間複雜度為O(n)。 2.二分搜尋演算法： (1)須事先排序。 (2)最好情形為1次。最差情形為(log2n)+1次。 (3)時間複雜度為O(log2n)。 三、結論： 任何搜尋演算法：時間複雜度≦O(n)

結語 高中資訊課程重視資訊科學基本概念 除必修2學分外，具充分開課彈性 教學方法強調理論與實務並重 重視學生對重要概念的理解 九年一貫電腦課程著重資訊科技應用 除必修2學分外，具充分開課彈性 資訊科技概論 ＋ 程式設計、應用軟體、專題 教學方法強調理論與實務並重 由實作中學習基本概念 重視學生對重要概念的理解 非細節、片段知識之記憶 培養學生對資訊科學的興趣為最重要目標

問題討論 vs 經驗分享 幸福不只是傳說， 學生快樂學習，教師歡喜授課。 你我都能做得到！ 謝謝各位指教