# Selection Sort

Selection Sort is a really easy to implement sorting algorithm, due to being inefficient on large datasets this algorithm is mostly used when memory is limited.

## 1.3.1. How

Selection sort work by having a list of numbers, it then goes through the list and finds the minimum number. When we finished looping the list we swap the founder minimum number with the current index.

As an example we take the following list:

```
2 9 8 3 5 6 1 0 4 7
```

We start at index 0, and start finding the minimal element in this sub list, which results in 0. We now swap index 0 with the index of the found minimum and get that we will swap 2 and 0 resulting into:

```
0 9 8 3 5 6 1 2 4 7
```

Now we are at index 1 (value 9), we find the minimum value again which is at index 6 (value 1), so we swap those 2

```
0 1 8 3 5 6 9 2 4 7
```

And we continue doing this until we have a sorted list:

```
0 1 2 3 4 5 6 7 8 9
```

For the implementation check paragraph `§3.4`.

## 1.3.2. Advantages and Disadvantages

**Advantages**

* Uses almost no swaps! $\Theta(n)$
* No extra space required, $O(n)$

**Disadvantages**

* Not Stable
* $O(n^2)$ performance
* Not adaptive

## 1.3.3. Performance

The performance analysis is really easy for selection sort, it will always perform $n^2$ because we loop the list no matter what.

| Worst Case | Average Case | Best Case |
| ---------- | ------------ | --------- |
| O(n2)      | O(n2)        | O(n2)     |

## 1.3.4. Implementation

### 1.3.4.1 Pseudo Code

```
for i=0, i<arraysize
    minIdx = i
    for j=i, j<arraysize
        if v[j] < v[minIdx]
            minIdx = j
    // swap
    swap(v[i], v[minIdx])
```

### 1.3.4.2 C++ Code

```
int minIdx;
for (int i = 0; i < v.size(); i++) {
    minIdx = i;

    for (int j = i; j < v.size(); j++) {
        if (v[j] < v[minIdx]) {
            minIdx = j;
        }
    }

    int temp = v[i];
    v[i] = v[minIdx];
    v[minIdx] = temp;
}
```

## 1.3.5. Benchmark

|                     | 100     | 1.000    | 10.000   | 100.000 | 1.000.000 |
| ------------------- | ------- | -------- | -------- | ------- | --------- |
| Random Elements     | 3.6e-05 | 0.003002 | 0.204347 | 19.3981 | -         |
| Ascending Elements  | 3.1e-05 | 0.002846 | 0.190501 | 19.1111 | -         |
| Descending Elements | 3.5e-05 | 0.002114 | 0.205667 | 20.0368 | -         |

## 1.3.6. Conclusion

We can clearly see that selection sort is a horrible sorting algorithm, however when swaps are really expensive and the memory is limited we could consider using this algorithm.


---

# 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://xavier-geerinck.gitbook.io/ugent-algoritmen-1/algorithms/13_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.