Bubble Sort (氣泡排序法) In PHP

# 前言

出來混總是要還的! 身為一個非本科的工程師, 就是自己找時間把自己缺的的都補上!
實作沒什麼好交代的, 直接看範例看註解吧!




# 概念解說

Bubble sort 可以說是最普遍被使用的的一種演算法。 它是一種基於比較性質的演算法, 也總是被歸類在最沒效率的排序演算法之一。 不過, 凡事都會有改進的空間。
在 bubble sort 中, 列表中的每一個品項都會跟其他的所有品項做比較, 視比較結果進行位置對調, 直到每個品項都跟其他的品項比較完畢。
可參考示意圖如下:

示意圖解析:
上圖為跑一輪的示意圖, 在每一輪中, 都會像示意圖中, 依序兩兩比較, 並視比較結果決定是否對調, 所以第一輪的目標便是將 list 中最大的數移到最右邊
若 list 中的 item 數量為 n, 那則需要跑 n 輪方能將整個 list 排序完畢




# 實作範例

# 理論版

  • Example code:
    function bubbleSort(array $arr): array { 
    $len = count($arr);

    // 每次兩兩比較, 共需比較 n-1 輪, 跑完即排序完畢
    for ($i = 0; $i < $len - 1; $i++) {
    // $j 從 0 開始, 即一開始 index 0 跟 index 1 比較
    // 接下來 index 1 跟 index 2 比較
    // 視結果決定是否對調位置
    for ($j = 0; $j < $len - 1; $j++) {
    if ($arr[$j] > $arr[$j + 1]) {
    $tmp = $arr[$j + 1];
    $arr[$j + 1] = $arr[$j];
    $arr[$j] = $tmp;
    }
    }
    }
    return $arr;
    }


# 改進一版

接下來我們來嘗試改進上面的版本。
可以從 bubble sort 的一個特點來著手, bubble sort 的每一輪外圈 iteration, 預設至少都會做一次調換動作, 換言之, 若沒有調換動作, 則後面剩下還沒跑的輪數都不用跑了
不囉唆, 直接看以下改進版範例:

  • Example code:
    function bubbleSort(array $arr): array { 
    $len = count($arr);

    for ($i = 0; $i < $len; $i++) {
    // 如上所敘, 這邊預設此輪不會有新的調換動作
    $swapped = FALSE;
    for ($j = 0; $j < $len - 1; $j++) {
    if ($arr[$j] > $arr[$j + 1]) {
    $tmp = $arr[$j + 1];
    $arr[$j + 1] = $arr[$j];
    $arr[$j] = $tmp;
    // 如果有進到條件判斷, 代表有進行調換動作, 因此將 $swapped 改為 true
    $swapped = TRUE;
    }
    }
    // 如果一輪跑完 $swapped 還是 false, 則代表列表都已經排序完畢, 後面的就不用再跑了
    if(! $swapped) break;
    }
    return $arr;
    }


# 改進二版

然而, 從以上的 example code 中觀察, 我們可以發現, bubble sort 的外圈每一輪都至少會將當輪最大的數移到最右邊, 換言之, 也可以說最右邊的數我們可以不必去判斷了
更精確地來說, 假設 $i = 1, 那代表 $i 從 0 - 1, 已經跑了一輪, 所以我們在內圈的比較上, 就可以少比較一輪
詳見以下 example code

  • Example code:
    <?php
    function bubbleSort(array $arr): array {
    $len = count($arr);

    for ($i = 0; $i < $len; $i++) {
    $swapped = FALSE;
    // 這裡新增了 $len - $i 的邏輯, 當外圈每跑一輪, 內圈就可以少比較一輪
    for ($j = 0; $j < $len - $i - 1; $j++) {
    if ($arr[$j] > $arr[$j + 1]) {
    $tmp = $arr[$j + 1];
    $arr[$j + 1] = $arr[$j];
    $arr[$j] = $tmp;
    $swapped = TRUE;
    }
    }
    if(! $swapped) break;
    }
    return $arr;
    }


# 最終改進版

  • 示意圖:

讓我們先來看看上面的示意圖。
假如今天外圈跑了兩輪, 我們完成了 97, 93 的排序, 雖然還沒跑第三輪, 但 92 明顯已位於正確的位置, 那依照我們上面的版本, 在下一輪還是會去比較 92, 是否可以省略這不必要的判斷?
或許, 我們可以記錄下, 當輪最後有進行對調動作的 index 位置, 假如第三輪最後只對調了 index 4, 5, 那代表 index 4 之後的數都已經是排序完成的, 換言之, 這個 index 之後的品項我們在後續的迴圈中都不需要去比較了
請看以下的最終改進版

  • Example code
    <?php
    function bubbleSort(array $arr): array {
    $len = count($arr);
    $count = 0;
    $bound = $len-1;

    for ($i = 0; $i < $len - 1; $i++) {
    $swapped = FALSE;
    $newBound = 0;
    // 如上所述, 這裡新增了 $j < $bound 邏輯
    // $bound 預設為 $len - 1, 但會隨著最後一次做對調的 index 位置而變化
    // 換言之, 假如上一輪最終對調 index 位置為 5, 那我下一輪開始時
    // 5 之後(含 5) 的 index 我都不需要去比較了
    for ($j = 0; $j < $bound; $j++) {
    $count++;
    if ($arr[$j] > $arr[$j + 1]) {
    $tmp = $arr[$j + 1];
    $arr[$j + 1] = $arr[$j];
    $arr[$j] = $tmp;
    $swapped = TRUE;
    // 這裏更新 $newBound, $newBound 會儲存最後一次有調整的 index
    $newBound = $j;
    }
    }
    // $bound 會在每一輪的外圈結尾時更新, 代表著上一輪外圈中, index 對調的最後位置
    // 換言之, 該位置往右的皆是已經排序完成的
    $bound = $newBound;

    if(! $swapped) break;
    }
    echo $count."\n";
    return $arr;
    }




# 改進結果比較

改設 list 為 20, 45, 93, 67, 10, 97, 52, 88, 33, 92
以下為個版本的比較次數:

解法 比較次數
一般 bubble sort 90
改進一版 63
改進二版 42
最終改進版 38




# 複雜度

最佳複雜度 $$\Omega(n)$$
最差複雜度 $$O(n^2)$$
平均複雜度 $$\Theta(n^2)$$
空間複雜度 $$O(1)$$




# 參考資料

PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP

Tree 實作 in PHP Selection Sort (選擇排序法) In PHP

留言

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×