[閱讀筆記] Algorithms to Live By - 排序 (Sorting)

 排序 (Sorting) - 依照順序排列

1. 在 1960 年代，有一項研究估計，全世界的電腦運算資源有 ¼ 以上用於排序。這點其實可以想見，因為排序對於處理各種資訊都非常重要。無論是找出最大或最小、最常見或最罕見、紀錄、製作索引、挑出重複物件，或者單純只要找出需要的資料，各種工作一開始通常都得先排序。

2. 追根究柢，排序的主要理由就是以好用的方式呈現物件，因此排序也對人類的資訊經驗極為重要：

排序例子	說明
E-mail 收件夾	依據寄信時間做排序
Yelp 餐廳搜尋結果	依據距離或評價最高做排序
Google	依據搜尋關聯性做排序，呈現最具關連的前十個網站，成為搜尋引擎霸主
Facebook / Twitter	依據文章張貼日期做排序

3. 1955 年 J.C. Hosken 在史上第一篇發表的排序論文中寫到：「為了降低每單位的成本，人類通常會加大運作規模。」這就是所謂的規模經濟，但是規模卻造成排序災難。排序規模加大時，排序的單位成本不減反增，導致嚴重的負規模經濟。例如，假設書架上有 100 本書，另外有兩個書架各 50 本，排好前者的時間一定大於後者，因此需要整理的書以及每本書可以放的空格，都多了一倍。需要處理的東西越多，狀況就越糟。

4. 要減少排序的辛苦和麻煩，重點是減少排序對象的數量。

🧦 以抽襪子為例

以湊成對的襪子為例，假設有 10 雙不同顏色與花紋的襪子，我要從洗乾淨的置衣籃湊成雙收好，我會先隨機抽 1 雙襪子，再平均抽 19 次，就能湊到第 1 雙；再隨機抽取 1 雙襪子，再平均抽 17 次，就能湊到第 2 雙，以此類推，最後要再置衣籃裡抽 110 次，就能把 20 支襪子湊成對。

要避免太多襪子造成排序困難的話，最佳方法就是經常洗襪子。以上述為例，10 天洗一次，需要排 110 次；3 天洗一次只需排 12 次、4 天洗一次需排 16 次 (+4)、5 天洗一次需排 30 次 (+18)。

5. 大O符號 (Big-O Notation)，又稱為漸進符號，是用於描述函式漸近行為的數學符號。更確切地說，它是用另一個（通常更簡單的）函式來描述一個函式數量級的漸近上界。在數學中，它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項；在電腦科學中，它在分析演算法複雜性的方面非常有用。假設你要辦個晚宴，邀請 n 名賓客：

打掃房子的時間 O(1)
為接待賓客而打掃房間所需的時間，與賓客人數無關，稱為「1的大 O】。寫成 O(1)， 又稱為常數時間 (constant time)，不理會打掃需要多久時間，只說明打掃時間與賓客人數無關。
烤肉在桌上傳遞一圈的時間 O(n)
傳遞一圈的時間是 n 個大 O，寫成 O(n)，又稱為線性時間 (linear time)，也就是說，賓客人數加倍，盤子傳到你面前的時間也加倍。
賓客互相擁抱的時間 O(n2)
如果賓客抵達時，會互相擁抱。第一位賓客只要跟你擁抱就好，第二位要擁抱兩次，第三位要擁抱三次。這時候稱為 n 平方的大 O，寫成 O(n2)，又稱為平方時間 (quadratic time)。
更糟糕的狀況
指數時間 (exponential time)：寫成 O(2n)，也就是每增加一位賓客，你的工作就會加倍。 階層時間 (factorial time)：寫成 O(n!)，通常是用暴力方法解決複雜問題。 (Ref.: https://reurl.cc/pmMnxa)

6. 氣泡排序法 (Bubble Sort) 與插入排序法 (Insertion Sort)

氣泡排序法 (Bubble Sort)

是一種簡單的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。 是最簡單瞭解和實作的排序算法之一，但它對於包含大量的元素的數列排序是很沒有效率的。 平均時間複雜度O(n2) 最壞時間複雜度O(n2) 最佳時間複雜度O(n) (Ref.: https://reurl.cc/Dv3nRE)

插入排序法 (Insertion Sort)

此排序法優點是比氣泡排序法更直覺，評價較好，缺點是其實沒有快多少。採取此方式時，每個位置還是都要插一次，每次插入平均時間需經過一半的位置，才能找到正確的位置。儘管插入排序法速度快了一點，花費時間仍是平方時間，沒有比氣泡排序快多少。 平均時間複雜度O(n2) 最壞時間複雜度O(n2) 最佳時間複雜度O(n) (Ref.: https://reurl.cc/qmNdzy)

7. 上述兩個看似合理且直覺的排序方法，搜尋時間都是平方時間 (quadratic time, O(n2))，排序對象一多就難以負荷。合併排序 (merge sort) 就是用來解決上述難題，它的複雜性介於線性時間和平方時間之間，更精確地說是線性對數時間 (linearithmic time, O(n log n))。屬於 Divide and Conquer 演算法，把問題先拆解 (divide) 成子問題，並在逐一處理子問題後，將子問題的結果合併(conquer)，如此便解決了原先的問題。

(Ref.: https://reurl.cc/bzEEnl)

8. 排序與運動賽事的類比

排序方法	運動賽事
Bubble sort	羽球、壁球等常用的排位賽 (ladder)，是依照排名順序列出的選手名單，每名選手可以挑戰前一名選手，如果獲勝，排名就對調。這就是運動界的 bubble sort，執行時間是平方時間。
Merge sort	NCAA 的單淘汰制 (tournament bracket)，每一輪比賽都淘汰一半隊伍，從 64 強、32 強、16 強、8 強、4 強以及決賽。這就是運動界的 merge sort，一開始為排序的隊伍兩兩比賽，接著不斷對併再對併。

9. 排序與搜尋的權衡：拿你絕對不會搜尋的資料來排序是浪費時間，搜尋沒排序過的資料則效率極差。排序資料所花的心力是先制行動，目的是讓我們日後不用花費心力搜尋資料。真正的平衡點應取決於狀況的確實參數，但如果說排序唯一價值是輔助日後查詢，就可以看出一個驚人事實：寧亂勿整。例如，現在電子郵件軟體的搜尋功能已經相當完善，當搜尋成本降低時，排序的價值就會跟著降低。

10. 不排序資料或許可以想成一種延遲行為，把責任推給未來的自己，讓他連本帶利地付出逃避的代價。不過整個狀況其實更加微妙，有時候混亂不只出於偷懶，而是最佳選擇。

11. 在奧運場上，拳擊選手必須冒著腦震盪的風險，比 O(log n) 次才能舉起金盃 (通常四到六次)；馬拉松選手則只需比一次。如果能以一個簡單數值來評量表現，就能以常數時間演算法來決定名次。從只能呈現排名的序數改成基數 (直接指定評定水準的方式)，就能自然地依序排列，例如 Fortune 500 的排名，不需公司間兩兩比較，只要有基準就能解決排序規模擴大產生的運算問題。

共通基準的例子	說明
⛵ 航海通行公約 -  依總噸位法則 (Law of Gross Tonnage) 決定	船的總噸位決定一切，小船要禮讓大船
🐟 魚類的默契 -  依 size 決定	越大的魚越有優勢，小魚要禮讓大魚；size 差不多則會互相逞兇鬥狠
🌏 G20 參與的成員國 -  依 GDP 決定	或許有人認為 GDP 太粗糙，但只要有一個單一參考點，就能很快解決國家地位問題，省去線性對數次數的鬥爭與決議
💰 Fortune 500 -  依公司營業額決定	以公司的營業額為排名，評選全美最大的 500 家公司的排行榜。

12. 在小規模族群中，線性對數次數的打鬥或許行得通，自然界的族群也經然如此。但再藉由兩兩比較決定地位的領域中，衝突次數將隨群體數目成長而快速增加。要讓成千上萬、甚至數百萬個群體生活在同一空間中，就必須跳脫出來，從序數變成基數 (或稱為基準)。人類和猿猴、雞等動物的差別是，以競賽取代打鬥。

13. 假設你是位正在撰寫論文的研究生，已知圖書館有數本需要隨時可參考的書籍，你會希望借閱這幾本書，放在宿舍的書桌上，而非需要參考時還要特地去圖書館一趟。此時，你的書桌就是電腦領域提到的 cache (快取)，當書桌上有可重複利用的書籍，你書桌的價值就越高；當你越常回圖書館找資料，工作進度越慢，書桌利用率越低，書桌價值就越低。