3.2.3 - Bubble Sort

1. 演算法

n筆資料由左而右依序兩筆資料相互比較，若前者大於後者則前後交換，共做n-1回合。若某一回合中完全無swap發生，則代表sort完成。

void Sort(char *arr){
    int n = strlen(arr);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]){ //swap
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
    }
}

演算法分析:

$input = \{5, 3, 8, 2, 6\}$

$i=0,\ j=0\ to\ 3\\ j=0 \Rightarrow \underline{3, 5,} 8, 2, 6\\ j=1 \Rightarrow \times \\ j=2 \Rightarrow3,5,\underline{2,8,}6 \\ j=3 \Rightarrow 3,5,2,\underline{6,8}$

$i=1,\ j=0\ to\ 2\\ j=0 \Rightarrow \times \\ j=1 \Rightarrow 3, \underline{2, 5,} 6, 8\\ j=2 \Rightarrow \times$

$i=2,\ j=0\ to\ 1\\ j=0 \Rightarrow \underline{2, 3,} 5,6, 8\\ j=1 \Rightarrow \times$

2. 性質

• Time Complexity:

  • Best Case: 資料恰好由小到大排列 $O(n)$

  • Worst Case: 資料恰好由大到小排列 $O(n^2)$

  比較次數＝ $(n−1)+(n−2)+...+1=\frac{n(n−1)}{2}$

  • Avg Case: $O(n^2)$

• Space Complexity: O(1)

Bubble sorting is a stable sorting method.