泡泡排序法的原理(數學歸納法)

幾日前看到網路有人談起一種荒謬的言論,說看到 PTT 某看板有人提起應徵 Java 工程師,考泡泡排序的事情,然後他談到自己的意見,是說寫個 class sort_helper { public list sort(list unsort) { } } 這樣來呼嚨,順便談談是怎樣的設計模式,反正寫一寫,可能面試官也看不懂。

我倒覺得不能這樣講道理。 Bubble sort 是很基本的演算法,如果連 Bubble sort 的原理都講不清楚,那麼還談什麼設計模式。

我用 Prolog 寫 Bubble sort 已經寫過好多次了,但還沒思考過 Bubble sort 的原理是什麼。隱約覺得,似乎可以用數學歸納法來談它。

前提:存在一種動作稱為「泡昇」,意思是一列數字,藉由每相鄰數字互相比較並且決定大小及擺放位置,可以達到整體「泡昇」的效果,每一次泡昇,凡較大的數字都朝向一邊靠近,而凡較小的數字則朝向另一邊靠近。整體來說,經過一次泡昇,則某一極端值(可能是最大值或最小值,看實際定義決定)會升到泡昇方向的終端位置。

因此, Bubble sort 可由以下二句,證明能有效排序:

  1. 只有一個數字的序列,是排序好的。
  2. 若有一個序列 N 已經排序好,又將額外一個數字 x 混入序列中,構成新序列 N’ 。
    1. 若數字 x 小於序列 N 的最小值,並且,將新序列 N’ 朝向極小值方向泡昇,則 x 會比序列 N 的任何一個數字先達到終端位置。
    2. 若數字 x 大於序列 N 的最小值,並且,將新序列 N’ 朝向極小值方向泡昇,則 x 會比序列 N 的每一個數字都較晚達到終端位置。
    3. 若數字 x 小於序列 N 的最小值,並且,將新序列 N’ 朝向極大值方向泡昇,則 x 會比序列 N 的每一個數字都較晚達到終端位置。
    4. 若數字 x 大於序列 N 的最小值,並且,將新序列 N’ 朝向極大值方向泡昇,則 x 會比序列 N 的任何一個數字先達到終端位置。
    5. 當序列 N 可分為三子集 P, Q, R ,且凡集合 P 的數字都小於 x ,凡集合 Q 的數字都等於 x ,凡集合 R 的數字都大於 x ,則
      1. 當我們將新序列 N’ 朝向極小值泡昇,對數字 x 與集合 Q 的數字來說,都比集合 P 的數字較晚達到終端位置(此根據 2B, 2C ),並且都比集合 R 的數字更早達到終端位置(此根據 2A, 2D )。
      2. 當我們將新序列 N’ 朝向極大值泡昇,對數字 x 與集合 Q 的數字來說,都比集合 P 的數字較早達到終端位置(此根據 2A, 2D ),並且都比集合 R 的數字較晚達到終端位置(此根據 2B, 2C )。

所以 Bubble sort 成立。

而因為泡昇可以化約為經過一個動作,使一列數字中的極端值浮現,所以 Insertion sort 恰好完全符合以上的證明。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Problem 並標籤為 。將永久鏈結加入書籤。