# Bubble Sort 氣泡排序法
###### tags: `LeetCode` `sort` `bubble sort`

:::info
:pushpin: 氣泡排序法是，從第一個元素開始，和相鄰數字比大小，若有需要就交換位置。因此也可稱為交換排序法。它的時間複雜度是 $O(n^2)$。
:::
---

{%youtube nmhjrI-aW5o %}

## 一、步驟觀察
* 遍歷未排序元素，作以下動作
* 與相鄰元素做比較
* 如果左邊大於右邊元素
* 交換位置
* 從後面向左移動標記


( 圖片來源 wiki )

## 二、實際操作
### 使用哪種資料結構：Array
* 設定 for loop 作為移動標記用 (右側開始)
* 遍歷未排序的元素
* 如果左邊元素 > 右邊元素
* 交換位置
* 向左移動標記

**邏輯：**

  arr <- an unsorted array of integers
  let len be the length of arr

  for i (len-1 to 1) do
    for j (0 to i-1) do
      if (arr[j]>arr[j+1]) then
        swap(arr, j, j+1)
      end if
    end for
  end for

  func swap(arr, leftIndex, rightIndex):
    temp = arr[leftIndex]
    arr[leftIndex] = arr[rightIndex]
    arr[rightIndex] = temp
  end func

**程式碼實作：**

debugger

function swap(arr, leftIndex, rightIndex) {
  temp = arr[leftIndex]
  arr[leftIndex] = arr[rightIndex]
  arr[rightIndex] = temp
}

function bubbleSort(arr) {

  for (let i = arr.length-1; i >= 1; i--) { // 已排序元素的控制器

    console.log(i)
    for (let j = 0; j <= i-1; j++) {
      if (arr[j] > arr[j+1]) {
        swap(arr, j, j+1)
      }
      console.log(arr)
    }

  }
}

bubbleSort([8, 9, 2, 5, 1])

<!-- ## 四、優化改善
內容 -->

## 三、時間複雜度 Big O
* 總共比較了 1+2+3+...+(n-1)
* 也就是 n*(n-1)/2
* 時間複雜度會忽略係數，所以為 $O(n^2)$