氣泡排序法

像這樣重新整理的舉動，除了對音樂愛好者來說有種情緒宣洩的效果，也可以用來迅速查詢及記資料，展現其中不同的特色。就像是整理電子郵件的時候，只要點一下就能選擇排列方式是依日期、寄件人、或是郵件主旨，這正是電子郵件的客戶端執行了一套有效率的演算法來做分類排序。

而在eBay上，你可以選擇要用「精準度」、「價錢由低到高」或「即將結束」來排序，這也是因為eBay用了有效率的分類排序演算法。至於谷歌，在它判斷了各個網頁與你搜尋的關鍵字匹配程度後，也需要迅速加以排序，用正確的順序顯示。人們夢寐以求的，就是能實現目標的高效演算法。

要排序一定數量的項目時，一種做法是盡可能窮盡所有排法，再一一檢查是否正確。假設我們就只蒐集了五張唱片，齊柏林飛船（Led Zeppelin）、皇后合唱團（Queen）、酷玩樂團（Coldplay）、綠洲合唱團（Oasis）和阿巴合唱團（Abba）各一張。光是五張專輯，就已經有一百二十種不同排法。六張會有七百二十種排法，到了十張，就有超過三百萬種排法。隨著唱片數量增加，排法的數量會急速成長，不管多痴狂的樂迷都不可能窮盡所有的排法：這單純就是件不可行的事。

▲ Photo Source

但幸好，你應該已經從自己過去的經驗發現，整理自己收藏的唱片、書籍或DVD其實是個P問題，也就是確實有某種可行的解決方案。在此，最簡單的演算法稱為「氣泡排序法」（bubble sort），原理如下。

讓我們先把那五張唱片依樂團原文名稱的縮寫L、Q、C、O和A來排序。氣泡排序法會從左到右檢查過去，只要相鄰的兩張順序不對，就互換位置。這個過程不斷重複，直到任何相鄰的兩張順序都正確，也就代表整個列表都排序完成。

第一次排序的時候，L在Q之前沒錯，所以位置不變，但比到Q和C的時候，就會發現順序有誤，於是兩者互換位置。氣泡排序法就這樣繼續，於是Q再與O互換、接著與A互換，到此時完成了第一次排序，結果是L、C、O、A、Q；Q已經排到了列表最後面的這個正確位置。

第二次排序，L與C互換、O與A互換，於是O也來到了正確的位置：C、L、A、O、Q。接著只要再兩次排序，A就會到達列表最前面，整個列表也成功依字母排序。

▲ Photo Source

我們把算式簡化一點好了。如果要排序五張唱片，就得將未經分類的唱片做四次排序，每次做四次比較。如果有十張唱片，就得排序九次，每次做九次比較。這意味著，我們每次排序過程中的工作量，幾乎就是需要排序的項目數量平方。

倘若你收藏了一堆唱片，這件事做起來當然還是相當費功夫，三十張唱片就得做幾百次的比較；然而，相較於暴力破解法需要列出天文數字的所有可能排法，採用氣泡排序法仍然省力不少。

雖然這已經是一大進步，但電腦科學家一般認為氣泡排序法的效率還是太低。在實際應用上，不論像是臉書的動態消息、或是Instagram的最新動態，隨時都有幾十億則發文必須依據這些科技龍頭的最新優先順序來排序顯示，於是簡陋的氣泡排序法也就被更新、更有效率的類似方法取代。例如「合併排序法」（merge sort），做法就是先將所有發文分成幾小批，經過迅速分類排序，再組合成正確的順序。

▲ Photo Source

2008年美國總統大選期間，馬侃（John McCain）成為候選人之後不久，受邀到谷歌發表演講，討論他的政策。谷歌當時的執行長施密特（Eric Schmidt）和馬侃開玩笑，說整個競選過程就像是谷歌的面試，接著就問了一個谷歌確實會問的面試問題：「如果只有2 MB的RAM，你要怎麼將一百萬個32位元整數進行排序？」馬侃看起來一頭霧水，而施密特玩笑開夠了，立刻問了下一個真正的問題。

六個月後，輪到歐巴馬（Barack Obama）來到谷歌接受考驗，施密特也拋出了同一個問題。歐巴馬看向觀眾，擦了一下眼睛，說道：「這個嘛，嗯……」施密特以為歐巴馬一時語塞，本來想接過話題，但歐巴馬直視著施密特的眼睛，繼續說著：「……不、不、不，我只是在想，絕不能用氣泡排序法吧」，全場的電腦科學家對此報以熱烈掌聲及歡呼。

歐巴馬的回應，反映出他出乎意料的博學多聞：他說了一個內行人才懂的笑話，笑點就在於這種排序演算法的效率有多麼低落。他的整個競選過程不斷顯露這種舉重若輕、信手捻來的魅力（唯有經過精心充分的準備才能做到），最後一路送他進白宮。

▲ Photo Source

 

本文節錄自《攸關貧富與生死的數學》

・作者：葉茲

・出版社：天下文化

・出版日期：2020/08/26

・更多書籍資訊請點此