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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/selection-sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.