# 氣泡排序法

在開始之前，我們先認識一下氣泡排序法在幹嘛。
### 跳跳Bubble Sort
{%youtube lyZQPjUT5B4 %}

---
### 排序DIY
接下來請到[這個網站](https://visualgo.net/en/sorting?slide=7-3)，按左下角的Create，自己輸入一串未排序的數字，再按左下角的Sort -> 按下Go，看看氣泡排序法如何幫你排序。行有餘力的同學，請觀察右下角的程式片段，看看程式執行的方式。

在執行的程式碼中，你會發現有個關鍵的步驟：**swap**
swap的意思是「交換」。在氣泡排序法中，只要左邊比右邊大，就會進行一次swap。問題來了：從哪邊開始交換、哪裡交換到哪裡，怎樣才算結束？

我們來看個動畫解釋吧：


在`6, 3, 0, 5, 1`五個數字的氣泡排序過程中，共經歷四個**回合(Pass)**，每一回合都是**由左至右**比較。
第一回合結束後，最後一個數字一定是最大的。第二回合結束後，倒數第二個數字一定是最大的。以此類推，在這個例子裡，第四回合結束後，陣列才完全排序好。

想一想，同樣是5個數字，怎樣的數列，不用這麼多回合，就可以排序完成？
反過來說，怎樣的數列，需要最多回合才能排序好？
兩個問題的答案，分別對應最佳狀況（Best Case）和最差狀況（Worst Case）。我們可以用兩種狀況分析這個排序法的**時間複雜度**，有興趣的同學可以自行Google。

了解氣泡排序法的原理之後，我們來看看流程圖表示法，思考程式該怎麼寫。

---
### 參考流程圖（出處：資訊科技教科書，科友版）

---

### 解題思路
(待)

---

### 參考程式碼
:::spoiler 程式碼1

#include <iostream>
using namespace std;

int main(){
    int a[1000];
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    int temp;
    bool ok = false;
    /*    i代表第i回合表示。    */
    for(int i = 1; i < n && !ok; i++){
        ok = true;
        /*    從第0項檢查到第i項    */
        for(int j=0; j < n-i; j++){
            /*    如果左項大於右項，就交換位置    */
            if (a[j] > a[j+1]){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                ok = false;
            }
        }
        
        /*    觀察每一輪輸出結果，數字排序有何變化     */ 
        cout << "round " << i << ": ";
        for(int k=0; k<n; k++){
            //cout << a[k] << ((k==n-1)? "\n":(k==i-1)?"|":" ");
            cout << a[k] << " |\n"[2*(k==n-1)+(k==n-i-1)];
        }
    }
    
    /*    輸出已排序陣列    */
    cout << "sorted array: ";
    for(int i=0; i<n; i++){
        cout << a[i] << ((i==n-1)? "\n":" ");
    }
    return 0;
}

:::

:::spoiler 程式碼2

#include <iostream>
using namespace std;

int main(){
    int a[1000];
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    int temp;
    bool ok = false;
    /*    每一回合檢查的最後一個數字用i表示。    */
    for(int i=n-1; i>0 && !ok; i--){
        ok = true;
        /*    從第0項檢查到第i項    */
        for(int j=0; j<i; j++){
            /*    如果左項大於右項，就交換位置    */
            if (a[j] > a[j+1]){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                ok = false;
            }
        }
        
        /*    觀察每一輪輸出結果，數字排序有何變化     */ 
        cout << "round " << n-i << ": ";
        for(int k=0; k<n; k++){
            cout << a[k] << " |\n"[2*(k==n-1)+(k==i-1)];
        }
    }
    
    /*    輸出已排序陣列    */
    cout << "sorted array: ";
    for(int i=0; i<n; i++){
        cout << a[i] << ((i==n-1)? "\n":" ");
    }
    return 0;
}

:::

#### 輸入

5
6 3 0 5 1

#### 輸出

round 1: 3 0 5 1|6
round 2: 0 3 1|5 6
round 3: 0 1|3 5 6
round 4: 0|1 3 5 6
sorted array: 0 1 3 5 6