CS T_T偷插電的資訊科學 – 排序演算法
【教 學 活 動 1】
活動目標：以活動體驗排序的進行方式。
活動時間：30分鐘
先備知識：無
授課年級：八年級
內容程度：初階
教學活動流程：
【活動：排紙杯遊戲】
- 準備水壺、不透明紙杯六個以及對應數量的不透明杯蓋。
- 在水壺中盛裝溫開水，由多到少的容量次序倒入紙杯中，將杯蓋蓋上，並將各杯正確的容量寫在杯底。
- 遊戲的目標是在不能偷看到正確容量的情況下，將紙杯依照由多到少的順序排列。讓學生分組，討論排杯子的策略後，派出代表進行。
- 按照正確性與時間的多寡分出勝負。
- 學生在這個活動中使用的策略屬於「氣泡排序法(bubble sort)」，只是他們並不會知道，教師留在後續介紹排序演算法時再引為例子即可。
參考資料：
- CS T_T偷插電的資訊科學
關鍵字：排序演算法、不插電教學法、偷插電的資訊科學
【教 學 活 動 2】
活動目標：認識基本的排序演算法。
活動時間：40分鐘
先備知識：無
授課年級：八年級
內容程度：初階
教學活動流程：
【活動：天平的排序遊戲】
- 使用輔助程式：http://163.22.72.196/html5/html5_sort_scale/sort_scale.html
- 畫面上共有八個瓶子，一開始並不能知道正確的容量，只能透過天平比較出孰輕孰重，讓學生嘗試是否能正確依照大小順序排列完成。
- 讓學生嘗試後，教師進行提問與提示，介紹不同的排序演算法後，讓學生分別使用不同的策略再進行操作。
- 選擇排序法(Selection sort)：先找到最輕的容器並擺在一邊。接下來，再從剩下的容器中挑出最輕的，並也擺到一邊。重復此動作直到所有的容器都被擺到同一邊。(註：學生在未接受提示之前，多是採取這種策略)
- 快速排序法(Quick sort)：從全部的物件中隨機挑出一個物件，然後把它放在天平的一端。然後將它與其他剩餘的物件一一比較，將較輕的放在左側，隨機選出的物件放在中間，較重的則分放在右側。(有可能在結束比較時，兩邊物件的數量不一樣)；選擇其中一側，將該側所有物件重複上面的步驟。再將另一側的物件也做一樣的處理。(記得記住一開始選擇的物件要保持在中間)剩餘的物件群一直重複這些步驟，直到每一群都只剩一個物件。一旦所有物件群都被分到只剩一個物件，所有物件便會被分成由最輕到最重。
- 插入排序法(Insertion sort)：從尚未排序的物件群中挑出一個物件，把它插入已排序物件群中正確的位置。隨著一次次的動作，未排序物件群的規模會越來越小，而已排序物件群的規模則會越來越大，直到所有物件都排序完成。玩撲克牌時就常常利用這種方式來理牌。(註：由於必須先知道瓶身的數字才能操作插入排序，因此在這個程式的設計機制上不適用)
- 氣泡排序法(Bubble sort)：一次又一次從頭到尾檢查整個物件群，如果兩個相鄰的物件順序不對，就把它們交換，整個物件群檢查完之後，再重頭開始檢查一次。如果沒有任何物件在檢查名單時被交換，就表示排序完成了。這個方法並不是很有效率，但是對某些人來說這種方法較容易理解。
- 合併排序法(Merge sort)：首先，將名單隨機分成大小相同的兩個群組(奇數個時則分成大小相近的兩份)。兩個群組都要分別做排序，最後再將兩個群組合併。
4. 進行討論，為什麼我們需要排序？東西不排序會如何？不同排序演算法的效率問題，以及為什麼我們需要更有效率的排序方法？
參考資料：
- CS T_T偷插電的資訊科學
關鍵字：排序演算法、不插電教學法、偷插電的資訊科學