> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/selection-sort.md).

# Selection sort

## 1.Selection sort 

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

## 2.Procedures 

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

## 3.Example code (Java) 

* 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**