> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/3-search/3.2-sorting/3.2.2-selection-sort.md).

# 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}$$&#x20;

$$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}$$&#x20;

### 2. 性質

* Time Complexity: $$O(n^2)$$&#x20;

  比較次數＝ $$(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}$$&#x20;
* Space Complexity: O(1)

Selection sorting is a **unstable** sorting method.

$$5,\ 5^*,\ 3 \Rightarrow 3,\ 5^*,\ 5$$&#x20;