[演算法] Bubble Sort 泡沫排序法

前言

今天要來紀錄排序經常用到的泡沫排序法。主要是參考了一些文章後，想要用更自己更容易理解的方式寫下來，一方面在檢查自己的邏輯是不是哪裡有問題，一方面也想要幫助跟我思維方式相近的讀者可以從這篇文章學習到泡沫排序法是怎麼一回事。

要解決的問題

假如現在有一個陣列，裡面是不按大小規則的數字，如果要將他們由小到大排序好，要怎麼做才好呢?

array = [5, 4, 3, 2, 1];

思維模式

兩個相鄰的元素倆倆比較，比較大的丟後面，比較小丟前面，一組組比下去，並且比個幾輪，最後順序就會是對的了。

長得比較高的排到後面啦!

上面的敘述可能有一些抽象，所以在進入真正的排序之前，想用生活化的例子來帶讀者進入泡沫排序的思維。

假設現在有A、B、C、D、E 五個人，五個人身高都不太一樣:

//五個人的身高資訊
A: 150,
B: 160,
C: 170, 
D: 180,
E: 190,

假如現在他們的排隊順序是長下面這樣，但我們希望可以改由矮到高來排的話，要怎麼做呢?

[E(190), D(180), C(170), B(160), A(150)]

那就兩個相鄰的人互相比較身高，比較高的就站到後面比較矮的站到前面，前一組人比完後，再換到下一組。幾輪下來應該就可以排好了吧? 接下來我們就照著這個規則排看看吧(下面會以身高直接代稱這些人，寫起來比較方便):

第一輪

為了釐清整個運作的邏輯，第一輪會一步步紀錄每次換位置的情況。

[180, 190, 170, 160, 150]// 第一位跟第二位比完互換位子
[180, 170, 190, 160, 150]//第二位跟第三位比完互換位子
[180, 170, 160, 190, 150]//第三位跟第四位比完互換位子
[180, 170, 160, 150, 190]//第四位跟第五位比完互換位子

第一輪換完後會長這樣: [180, 170, 160, 150, 190];(最高的排到最後面了)

第二輪

第二輪換完後會長這樣: [170, 160, 150, 180, 190];(第二高的排到倒數第二位了)

第三輪

第三輪換完後會長這樣: [160, 150, 170, 180, 190];(第三高的排到倒數第三位了)

第四輪

第三輪換完後會長這樣: [150, 160, 170, 180, 190];(第四高的排到倒數第四位了)

經過四輪的互換後，大家總算按照身高由矮到高排隊了。並且我們還發現了兩個規律，

1. 第一個規律:

第一輪會找出第一高的放到最後一位，第二輪會找出第二高的放到倒數第二位...以此類推。

換言之:
第一輪排序是從第一個人依序比較到第五個人 (index0 到 index4);
第二輪排序是只用從第一個人比較到第四個人 (index0 到 index3);
第一輪排序只用從第一個人比較到第三個人 (index0 到 index2);
第一輪排序只用從第一個人比較到第二個人 (index0 到 index1);

2. 第二個規律:

如果要確保完整排序完的話，至少要跑 (全部的人數 - 1) 輪。不然就有可能會沒完整排序。用程式語言來說的話，就是要跑 (陣列長度 -1) 輪。

依照以上的規則，我們就來試看看用 JS 寫看看這個邏輯吧 !

程式邏輯來啦 !

先寫兩兩比較的邏輯:

function bubbleSort(arr){
    let length = arr.length; 
    // 找出陣列長度
    // 在下面這個迴圈裡倆倆比較前後兩個元素的大小
    // 比較大的就丟後面，小的丟前面
    for(let i = 0; i<length - 1; i++){
        let tempValue;
        if(arr[i] > arr[i + 1]){ 
            tempValue = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = tempValue;
        }
    }
    return arr
}

在前面的步驟裡，我們倆倆比較了前後的元素，但是只比較了一輪，根據前面推倒出來的兩個規律:

1. 第一個規律: 第一輪會找出第一高的放到最後一位，第二輪會找出第二高的放到倒數第二位...以此類推。

換言之:
第一輪排序是從第一個人依序比較到第五個人 (index0 到 index4);
第二輪排序是只用從第一個人比較到第四個人 (index0 到 index3);
第一輪排序只用從第一個人比較到第三個人 (index0 到 index2);
第一輪排序只用從第一個人比較到第二個人 (index0 到 index1);

1. 第二個規律: 如果要確保完整排序完的話，至少要跑 (全部的人數 - 1) 輪。不然就有可能會沒完整排序。用程式語言來說的話，就是要跑 (陣列長度 -1) 輪。

根據第二個規律，我們至少要跑 (陣列長度 -1) 輪；再來，根據第一個規則，每一輪都可以少比較一個元素，所以程式要再改寫成:

function bubbleSort(arr){
    let length = arr.length;
    // 要確保執行 (陣列長度 - 1) 輪，所以加上了 while 
    // 並且 length 在每一輪都會減一，所以每一輪都可以
    // 少比較一個元素。
    while(length > 1){
        length--
        for(let i = 0; i<length; i++){
            let tempValue;
            if(arr[i] > arr[i + 1]){
                tempValue = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tempValue;
            }
        }
    }
    return arr
}

這麼做就大功告成啦 !

資料來源: 氣泡排序法（Bubble Sort）：利用兩兩元素交換位置達到排序