3.2.2 - Selection Sort

1. 演算法

從第$i$筆到第$n$筆資料中挑出最小值，與第$i$筆資料交換。

void Sort(char *arr){
    int n = strlen(arr);
    int min;
    for (int i = 0; i < n; i++){
        min = i;
        for (int j=i; j < n; j++){   //尋找最小值
            if (arr[j] < arr[min]){
                min = j;
            }
        }
        if (min != i) {     //與最小值交換
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

演算法分析：

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

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

2. 性質

• Time Complexity: $O(n^2)$

  比較次數＝ $(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}$
• Space Complexity: O(1)

Selection sorting is a unstable sorting method.

$5,\ 5^*,\ 3 \Rightarrow 3,\ 5^*,\ 5$