擁抱「資料結構」的「演算法」(19) - 氣泡排序與選擇排序

 

前言

首先，先來介紹最常見的排序法，顧名思義就是將數字由大到小重新排列

生活常識

身為東方人，最喜歡作的動作大概就是比較了吧XD，跟兄弟姊妹比，跟同學比，甚至連鄰居也難逃被拿去比較，那要比什麼呢？無非是成績啦，或是身高、體重也會加入評比範圍，想必大家都有經歷過這個過程吧



圖片來源：https://www.pexels.com/zh-tw/photo/4412924/

以前安排學校的班級座位時，都會請同學們依照身高排列好，一直覺得這個過程很殘酷，因為很容易知道誰是班上最高，但同時，也會知道班上誰最矮XD

專業知識 - 排序 Sort

排序的是一種很常見的行為，主要是將資料由小到大、或由大到小排列，根據資料量的多寡又分為：

  • 內部排序：資料量小，可在記憶體內完成排序
  • 外部排序：資料量大，需透過硬碟才能完成排序

而相關的排序演算法有非常多種，其優點缺點與執行速度的快慢表現如何，會在這幾天逐一介紹

  • 初等排序
  1. 氣泡排序法 Bubble Sort
  2. 選擇排序法 Selection Sort
  3. 插入排序法 Insertion Sort
  4. 謝耳排序法 Shell Sort)
  • 高等排序
  1. 快速排序法 Quick Sort
  2. 合併排序法 Merge Sort
  3. 堆積排序法 Heap Sort

專業知識 - 氣泡排序 Bubble Sort

又稱交換排序法，顧名思故就是與相鄰的資料兩兩比較，如果數字較大者在前面，則需交換位置到後面，這樣一來可確保，數字最大者會排在最後面

例子

假設目前有 5 個數字，排列情況由大到小為：9, 8, 7, 6, 5 以氣泡排序將排列改為由小到大

第一次掃描 9, 8, 7, 6, 5
1.　9 與 8 相比，發現 9 比 8 大，所以交換位置，排列狀況為： 8, 9, 7, 6, 5
2.　9 與 7 相比，發現 9 比 7 大，所以交換位置，排列狀況為： 8, 7, 9, 6, 5
3.　9 與 6 相比，發現 9 比 6 大，所以交換位置，排列狀況為： 8, 7, 6, 9, 5
4.　9 與 5 相比，發現 9 比 5 大，所以交換位置，排列狀況為： 8, 7, 6, 5, 9 (最大的 9 在最後面)



第二次掃描 8, 7, 6, 5, 9
1.　8 與 7 相比，發現 8 比 7 大，所以交換位置，排列狀況為： 7, 8, 6, 5, 9
2.　8 與 6 相比，發現 8 比 6 大，所以交換位置，排列狀況為： 7, 6, 8, 5, 9
3.　8 與 5 相比，發現 8 比 5 大，所以交換位置，排列狀況為： 7, 6, 5, 8, 9



第三次掃描 7, 6, 5, 8, 9
1.　7 與 6 相比，發現 7 比 6 大，所以交換位置，排列狀況為： 6, 7, 5, 8, 9
2.　7 與 5 相比，發現 7 比 5 大，所以交換位置，排列狀況為： 6, 5, 7, 8, 9



第四次掃描 6, 5, 7, 8, 9
1.　6 與 5 相比，發現 6 比 5 大，所以交換位置，排列狀況為： 5, 6, 7, 8, 9


兩兩相比較，都沒有發生交換的動作時，就代表資料已由小至大排列完成

分析

  • 最壞的情況
    資料是反序排序，如上述例子 https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E2)
    第一次掃描做了 4 次交換 = (5-1)次 = (n-1)次，n = 數字個數
    第二次掃描做了 3 次交換 = (5-2)次 = (n-2)次
    第三次掃描做了 2 次交換 = (5-3)次 = (n-3)次
    第四次掃描做了 1 次交換 = (5-4)次 = (n-4)次
    總次數為 = (n-1) + (n-2) + ... + 2 + 1 = https://chart.googleapis.com/chart?cht=tx&chl=n(n-1)%2F2，取最高項次https://chart.googleapis.com/chart?cht=tx&chl=n%5E2

  • 最好的情況
    資料原先就已經排列好，則只需做 n-1 次的比較，發現沒有交換情況，時間為 O(n)

專業知識 - 選擇排序 Selection Sort

選擇排序重點在於選，此演算法會直接挑選出全部數值中的最小值出來做比較，若大小相反則交換，不會進行兩兩相鄰的比較

例子

假設目前有 5 個數字，排列情況由大到小為：9, 8, 6, 5, 7 以選擇排序將排列改為由小到大

  • 第一個步驟 9, 8, 6, 5, 7
    鎖定第 1 個位置，在 8 6 5 7，4 個數字中選擇最小值，選到 5
    5 比 9 小，將 5 與 第 1 個位置的 9 交換，得到 5, 8, 6, 9, 7



  • 第二個步驟 5, 8, 6, 9, 7
    鎖定第 2 個位置，在 6 9 7，3 個數字中選擇最小值，選到 6
    6 比 8 小，將 6 與 第 2 個位置的 8 交換，得到 5, 6, 8, 9, 7



  • 第三個步驟 5, 6, 8, 9, 7
    鎖定第 3 個位置，在 9 7，2 個數字中選擇最小值，選到 7
    7 比 8 小，將 7 與 第 3 個位置的 8 交換，得到 5, 6, 7, 9, 8



  • 第四個步驟 5, 6, 7, 9, 8
    鎖定第 4 個位置，在 8，1 個數字中選擇最小值，選到 8
    8 比 9 小，將 8 與 第 4 個位置的 9 交換，得到 5, 6, 7, 8, 9



分析

  • 最壞的情況 https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E2)
    第 1 個位置要與4 個數中找到最小值 = 找(5-1)次 = (n-1)次，n = 數字個數
    第 2 個位置要與3 個數中找到最小值 = 找(5-2)次 = (n-2)次
    第 3 個位置要與2 個數中找到最小值 = 找(5-3)次 = (n-3)次
    第 4 個位置要與1 個數中找到最小值 = 找(5-4)次 = (n-4)次
    找最小值的總次數為 = (n-1) + (n-2) + ... + 2 + 1 = https://chart.googleapis.com/chart?cht=tx&chl=n(n-1)%2F2，取最高項次https://chart.googleapis.com/chart?cht=tx&chl=n%5E2

  • 最好的情況
    與最壞情況相同 https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E2)

今日小結

氣泡與選擇排序法算式很經典的排序演算法，在書籍中常常看到它們的介紹，也非常簡易好懂，明天再來介紹插入與合併演算法

今日謎題

最近的國慶日有一場音樂演奏會，聽說會出現某種樂器
你能由小至大排序以下數字 15, 3, 12, 5, 12，並根據下表推算出是哪一種樂器嗎？



昨日解謎

謎題說明：根據圖片下方，有寫 FIND CODE，這邊可能會誤以為是要找程式碼，但其實不是，真正要找的是 C、O、D 與 E 在表格內的分佈，並把它們相連起來，即可得到 ALGO(演算法的縮寫)




留言

張貼留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

以下是自己的 CPE 一顆星選集 解題紀錄 (共有 49 題) 每次考試都會從一顆星選集中抽 1 提出來考 算是比較能把握的部分，重點筆記整理如下 內容包含題目說明、程式碼、註解說明、解答、考古題統計(下方土黃色日期) 解題使用的程式語言是  JAVA  目前有提供 10 題的試閱 另有提供完整 49 題的完整解答 ( pdf 檔 )， 共 305 頁， 售價 $399 元 ， 若有需要請來信購買 greens2314@gmail.com 推薦閱讀： 建議熟讀 java 基本觀念，與使用 eclipse 練習， 等熟悉之後再到瘋狂程設考試(一定要懂如何查 JAVA API 與使用英漢字典) Java 考試常用的方法或類別 Eclipse 常用小技巧 CPE 一顆星選集： 編號 | 題目名稱 | 歷屆考古題日期 1. Vito's family (CPE10406, UVA10041) 2024/04/23 可與第 40 題一起看 2. Hashmat the brave warrior (CPE10407, UVA10055) 3. Primary Arithmetic (CPE10404, UVA10035) 　 2011/05/25、2023/03/21 4. The 3n + 1 problem (CPE10400, UVA100) 　 2010/06/09 5. You can say 11 (CPE10460, UVA10929) 　 2011/12/20 6. Bangla Numbers (CPE10414, UVA10101) 　 2018/12/18 7. List of Conquests (CPE21924, UVA10420) 　 2019/03/26 　　可與 第 8, 11, 43 題一起看 字元與字串 8. What's Cryptanalysis? (CPE10402, UVA10008) 　　可與 第 7, 11, 43 題一起看 9. Decode the Mad man (CPE10425, UVA10222) 　 2021/10/19 10. Problem J: Summing Digits (CPE10473, UVA11332) ...
Read more »

Visual Studio 自動排版格式化程式碼

圖片
在團隊開發過程中，什麼時候是程式碼瘋狂修改的階段呢， 無非就是Code Review了，有時候卡個幾天或是幾個月都是有可能的， 裡面常出現的comment，每次幾乎都會出現的就是排版的問題， 例如空白多一個少一個，括號還沒換行等等的小瑕疵， 對於心思不夠細膩的人而言，真的十分的惱人 團隊中喜歡將大括號換行， 例如： if(true) {   //code } else {   //code } 那也許有些團隊喜歡： if(true){   //code }else{   //code } 有時候不只括號要不要換行，連else要不要換行都有各自的喜好， 所以有時候要統一使用團隊規定的喜好真的會有眼殘的時候， 自己檢查老半天可能還是有漏網之魚， 但現在不用擔心啦！ 只要使用Format 格式化文件就能為你分憂解勞， 設定方式如下： 編輯 > 進階 > 格式化文件 Visual Studio會根據你的環境設定幫你自動重新排版 設定方式如下： 工具 > 選項 切換到 文字編輯器 > C# >程式碼樣式 > 格式化 > 新行 這邊可以設定很多換行的邏輯， 將對應的項目打勾跟取消勾選，下面的黑色區域會顯示排版的格式， 可根據自己或是團隊的喜好去做調整，即可自動排出你想要的格式囉！ 如果覺得 編輯 > 進階 > 格式化文件 這個選項太難找到， 可以參考這篇文章，將他加入在明顯的工具列區域喔 http://greens2314.blogspot.tw/2017/09/visual-studio-2015.html
Read more »

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明

圖片
    👉   CPE 一顆星選集列表(49題) 題目說明與解答 題目 Vito 在紐約有非常多的親戚，他希望在紐約找到一間房子，這間房子到每個親戚家的距離總和，要是最少的距離 輸入說明 輸入資料包含很多筆測試資料 每筆測資，包含親戚數量與每位親戚家的街號 親戚數量介於1~499、街道範圍介於1~29999 多位親戚可住在同一條街 輸出說明 針對每筆測試資料，計算出 Vito 到每位親戚家的最短距離總和 街與街的距離 = 街道數字相減取絕對值 解題技巧 中位數 是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數，其意義是在所有資料中居於中間位置的代表 排序 街道的數字同時代表距離，透過排序，可得知中位數 解題過程 取得輸入 取得資料筆數 根據資料筆數取得親戚數量 根據親戚數量取得街道編號 將街道編號存入陣列中 將親戚的街道位置 由小至大 排序 呼叫 Arrays 類別提供的 sort() 方法 https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html 假設親戚有 5 位，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街 計算中位數 中位數在陣列中的索引 = 親戚數量 / 2 假設親戚有 5 位( 奇數) ，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街，其中 4 為中位數，中位數有 1 個 5位親戚 / 2 = 2.5，取整數，陣列索引 2 的位置，儲存的是第 4 街 假設親戚有 4位 (偶數) ，分別住在：2、5、8、4街 排序後為：2 、4、5、8街，其中 4 或 5 為中位數， 中位數有 2 個，擇一即可 4位親戚 / 2 = 2，陣列索引 2 的位置，儲存的是 5 街 計算最小距離總和並印出 宣告 sum 變數，統計距離 使用 foreach 將各街道編號 減掉 中位數編號，取絕對值並進行家總 取絕對值要呼叫  Math.abs ()  方法 奇數情況 ： 中位數有 1 個 假設親戚有 5 位   ，分別住在： 2 、2、 4 、5、8 街 中位數 4 ，Vito 住在 4 街，到其他親戚家的距離總和即是最小值 9   偶數情況 ： ...
Read more »