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