# Algorithm 演算法 - 排序系列 Selection sort 選擇排序

選擇排序是反覆進行「搜尋陣列中的最小值，將它與最左邊的元素對調」的操作。搜尋數列中的最小值使用線性搜尋。以下是圖示解釋，可以看到在每一步中我們都選擇了陣列中的最小值，然後慢慢的排序出來。 

![selection-short.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1645364315504/LOc9cTdE3.png)

### 範例

數值：`6 1 7 8 9 3 5 4 2`

1. 利用線性搜尋找出最小值：`1`，然後將 1 跟最左邊的數值 `6` 對調 => `1 6 7 8 9 3 5 4 2`
2. 從除了 `1` 之外剩下的數列重複第一步驟 => `1 2 7 8 9 3 5 4 6`
3. 一直重複動作直到排序完成

因為搜尋的數量是 `(n-1) + (n - 2) + ... 1 = (n**2) / 2`，所以 Time complexity 是 `O(n**2)`

### 程式範例

#### Go

```go
func selectionSort(nums []int) {
    arrLen := len(nums)

    for i := 0; i < arrLen; i++ {
        minIndex := i
        for j := i + 1; j < arrLen; j++ {
            if nums[minIndex] > nums[j] {
                minIndex := j
            }
        }

        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    }
}
```

#### JavaScript

```javascript
function selectionSort(nums) {
    const arrLen = nums.length;

    for (let i = 0; i < arrLen; i++) { 
        let minIndex = i;
        for (let j = i + 1; j < arrLen; j++) { 
            if (nums[minIndex] > nums[j]) {
                minIndex = j;
            }
        }

        let temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
}
```

#### Kotlin

```kotlin
fun selectionSort(nums: IntArray) {
    val arrLen = nums.size
    for (i in 0..n-1) {
        var minIndex = i
        for (j in n-1 downTo i) {
            if (nums[minIndex] > nums[j]) {
                minIndex = j
            }
        }

        var temp = nums[i]
        nums[i] = nums[minIndex]
        nums[minIndex] = temp
    }
}
```

#### PHP

```php
<?php
function selectionSort(array $nums): array
{
    $len = count($nums);

    for ($i = 0; $i < $len; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($nums[$minIndex] > $nums[$j]) {
                $minIndex = $j;
            }
        }

        $tmp = $nums[$i];
        $nums[$i] = $nums[$minIndex];
        $nums[$minIndex] = $tmp;
    }
}
```

#### Python

```python
def selectionSort(nums -> list):
    arr_len = len(nums)

    for i in range(arr_len):
        min_index = i
        for j in range(i+1, arr_len):
            if nums[min_index] > nums[j]:
                min_index = j

        nums[i], nums[min_index] = nums[min_index], nums[i]
```

#### Rust

```rust
pub fn selection_sort(arr: &mut [i32]) {
    let len = arr.len();

    for i in 0..len {
        let mut min_index = i;
        for j in (i + 1)..len {
            if arr[min_index] > arr[j] {
                min_index = j;
            }
        }

        arr.swap(i, min_index);
    }
}
```

#### Swift

```swift
public mutating func selectionSort(nums: inout [Int]) {
    for i in 0 ..< nums.count - 1 {
        var minIndex = i

        for j in i + 1 ..< nums.count {
            if nums[j] < nums[minIndex] {
            minIndex = j
            }
        }

        swapAt(i, minIndex)
    }
}
```

##### Reference

- https://www.programiz.com/dsa/selection-sort
- https://www.geeksforgeeks.org/selection-sort/