# Selection sort

## 1.Selection sort&#x20;

* At each iteration 1 element is selected and compared with every other element in the list to find the smallest one&#x20;
* Selection sort selects one element at a time, compare it to all other elements in the list&#x20;
  * The correct position for that selected element is found before moving on to the next element&#x20;

## 2.Procedures&#x20;

1. 一開始選擇list中的第一個元素, 將這個元素依序與每個其他元素相比, 若是比較大則swap, 找到最小的元素&#x20;
2. 選擇第2個元素與其他剩下的元素比較, 找到最小的元素&#x20;
3. 重複1 \~ 2作完整個序列

## 3.Example code (Java)&#x20;

* SelectionSort method

```
public static void selectionSort(int[] listToSort) {
    for (int i = 0; i < listToSort.length; i++) {
        for (int j = i + 1; j < listToSort.length; j++) {
            if (listToSort[i] > listToSort[j]) {
                swap(listToSort, i, j);
                print(listToSort);
            }
        }
    }
}
```

*   Helper method

    * Swap

    ```
    public static void swap(int[] listToSort, int iIndex, int jIndex) {
        int temp = listToSort[iIndex];
        listToSort[iIndex] = listToSort[jIndex];
        listToSort[jIndex] = temp;
    }
    ```

    * Print



    ```
    public static void print(int[] listToSort) {
        for(int el: listToSort) {
            System.out.print(el + ",");
        }
        System.out.println();
    }
    ```

## 4.Complexity

* In the worst case "N" elements are checked for every selected element
  * Complexity of selection sort is **O(N^2)**
* It is **not a stable sort**: entities which are equal might be re-arranged
* It **takes O(1) extra space**, it sorts in space
  * 因為用原本的list儲存
* It makes **O(N^2) comparisons** and **O(N) swaps**
* It's **not adaptive sort**

