泡沫排序法（Bubble-sort）

泡沫～

概念

兩兩做比較，如果右邊比左邊大就換位置，最後在最右邊的數字就是「最大值」。

因為很像泡泡一樣往上飄，故得到「泡沫排序法」這個名稱。

流程圖：

步驟

let swapped = null
let sortedCounter = 0
let total = array.length
do 
  swapped = false
  let unsortedNumberCount = total - sortedCounter
  for i 1 to unsortedNumberCount-1
    if leftElement > rightElement
      swap(leftElement, rightElement)
      swapped = true
  end for
  swappCount++
while swapped

令 swapped = null（一個 flag，判斷是否排序完畢）
令 sortedCounter = 0（計算已經有幾個數字排序完畢）
令 total = array.length（全部有幾個數字）

do
  swapped = false （設定 flag 初始值，如果沒被更新就不會有下一圈）
  令 unsortedNumberCount = 尚未排序的數字數量
  遍歷 1 到 unsortedNumberCount - 1
    如果左邊數字 > 右邊數字
      把兩個數字交換
      swapped = true（設定 flag，代表還沒排序完畢）
  迴圈結束
  sortedCounter++（更新已排序數量）
while swapped

實作

function bubbleSort(arr) {
  // 判斷用的 flag
  let swapped = null
  // 已經排序好的數量 
  let sortedCounter = 0
  // 總數
  let total = arr.length

  // 排序
  do {
    // 設定 flag 初始值
    swapped = false
    // 未排序的數字總數
    const unsortedNumberCount =  total - sortedCounter
    // 第一次遍歷： i from 0 to 18
    // 第二次遍歷： i from 0 to 17
    for (let i=0; i<unsortedNumberCount-1; i++) {
      // 左邊 > 右邊就交換位置
      if (arr[i] > arr[i+1]) {
        let temp = arr[i]
        arr[i] = arr[i+1]
        arr[i+1] = temp
        // 更新 flag，代表要在跑一次迴圈
        swapped = true
      }
    }
    // 已排序好的數量 + 1
    sortedCounter++
  } while (swapped)

  // 回傳結果 
  return arr
}

/*
  比較不同的排序法：
  bubble: 13 次迴圈
  selectionSort 20 次迴圈
*/
const numbers = [5, 44, 23, 3, 42, 4, 2, 29, 3, 16, 3, 48, 35, 44, 23, 24, 20, 45, 26, 6]
console.log(bubbleSort(numbers))
/*
  [
     2,  3,  3,  3,  4,  5,  6,
    16, 20, 23, 23, 24, 26, 29,
    35, 42, 44, 44, 45, 48
  ]
*/