從 ReactiveCocoa 開始，一點一點的開始進入 Functional 的世界。就算是我這個從國小就開始學程式語言的人來說，的確，Functional 的思維並不是這麼容易上手的，但更深入瞭解會發現其實真正的原因是我們早就習慣 imperative 的思考方式（抱歉，我實在找不到更簡易的說法）。這兩三年 Functional 在軟體業的各種崛起，剛好跟上這波潮流的我，決定要來寫一些相關心得，希望讀者可以看了以後可以互相指教。喔對了，這邊會用 javascript es6 的 syntax 來寫 sample code，還有，這篇並不適合初學者閱讀，而如果你是頗有經驗的 programmer ，就請多多賜教。
Here is the English version of this article.
那麼就從一個小短文開始吧！今天的題目是 sort。啥？sort 不就….call sort function 而已嗎？No no no！以我的觀點來說，會不會寫 sort 演算法可以說是判斷會不會寫程式的重要指標，因為其實我們都會排大小順序，而且寫程式就是能夠清楚的了解自己在幹嘛，並且能夠把這寫成 code，而且不會太複雜，也不會太簡單。接下來我會介紹三種 sort 演算法跟實作，但最後才會寫明什麼是什麼。
試著想想自己怎麼做排序吧！手上拿到樸克牌的時候會怎麼做？從小的開始挑，3 都挑起來以後挑 4，最後是 A 跟 2。那對應到程式碼呢？假設現在有個長度為 n 的 array，如果共用一個 array 的話就是：先專注在第一個 element ，然後往後看，有比現在這個小的就交換，比完一輪以後就可以確認第一個 element 一定是最小的，然後這樣做個 n 輪，就排好了。這是我想到最靠近我直覺思考方式的做法。
第二種，相鄰的兩個相比，如果左邊比較大，就交換。總之重複這個步驟很多遍直到沒有交換發生就代表排完了。
再來是第三種：首先先抓第一個，然後剩下的比手上小的放左邊，比較大的放右邊，然後再分別對左右兩堆做一樣的事情，一直重複到全部排完。
好啦！三個都講完了，不知道各位覺得哪個比較簡單好想呢？
在說明個別演算法的正式名稱之前，先來稍微分析一下：
首先，第一跟第二種必須要宣告 i, j 兩個變數，還有相對應的兩層迴圈，要檢查邊界，j 的初始值跟 i 有關，第三種以上說的都沒碰到。
再來，第一跟第二種都需要處理交換變數問題，所以語言本身沒有支援的話就要宣告第三個變數 t，一樣，第三種沒碰到這個問題。實際上我在寫這些範例的過程中，交換的部分還不小心寫錯了。
最後，第三種用在 function 的實作中用到了自己，也就是遞迴的概念，而前兩種沒用到，相信大部分的人學程式語言的過程中，都對遞迴有種恐懼感。
那麼來揭曉什麼是什麼啦～照順序這些排序演算法分別是：
- selection sort
- bubble sort
- quick sort
什麼！？quick sort 這麼簡單？對，就是這麼簡單。平常隨便找的 quick sort 為什麼看起來這麼複雜呢？主要是因為想要對記憶體使用最佳化，不過要討論篇幅會變得太長。另外你也可以說用 filter, concat 這些 function 有點作弊，不過基本上所有 pure/impure functional language 都內建這個 function，而且討論不同程式語言之間的公平性沒什麼太大意義。
回到題目：Functional，我認為第三種的 quick sort 實作之所以這麼精簡，是因為用了 functional 計算思維，所謂宣告式 (declarative) 的描述：我要比較小的在左邊，比較大的在右邊。然後剩下的交給電腦處理。當然並不是說 selection sort 跟 bubble sort 不能使用 functional 的方式實作，但稍微想一下就知道，在使用 functional 的思考方式下，quick sort 才是最直覺的演算法，好巧不巧又剛好是最快的那個（這邊只考慮一般狀況）。
那麼這篇就到這邊，下一篇相關的大概可能或許會來討論 DP 跟 Recursion 之間的關係。
UPDATE 2016/06/06: Fix bubble sort. Thanks to Chieh-Min Wang
