演算法 — Bubble Sort (氣泡排序法) — PHP. 出來混總是要還的! 身為一個非本科的工程師… | by Ray Lee | 李宗叡 | Learn or Die

Ray Lee | 李宗叡

Published in

Learn or Die

6 min readDec 5, 2020

# 前言

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

# 概念解說

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;
}