# Selection Sort

## Background

Selection sort is an intuitive comparison-based sorting algorithm. Like bubble and insertion sort, it maintains a sorted and unsorted region. It repeatedly finds the smallest (or largest) element in the unsorted region and places it in its correct *final* position.

![Selection sort](https://3573042214-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F3J8TQPaZW7TlilOSUhgs%2Fuploads%2Fgit-blob-6f328c78fb5fa301493af43664cf44940be9c655%2FSelectionSort.png?alt=media)\
\&#xNAN;*Source: HackerEarth*

### Implementation Invariant

**At the end of the kth iteration, the smallest k items are correctly sorted in the first k positions**.

Unlike insertion sort, elements placed in the sorted region are in their *final* positions and will not be displaced by future iterations.

At the end of the (n-1)th iteration, the smallest (n-1) items are correctly placed, leaving the last item correctly positioned. Therefore, (n-1) iterations suffice.

## Complexity Analysis

| Case    | Time    | Space  |
| ------- | ------- | ------ |
| Worst   | `O(n²)` | `O(1)` |
| Average | `O(n²)` | `O(1)` |
| Best    | `O(n²)` | `O(1)` |

Regardless of how sorted the input is, selection sort runs the minimum-finding algorithm (n-1) times. Finding the minimum in an array of length m takes `O(m)` time. Total: `n + (n-1) + ... + 2 = O(n²)`.

**Note**: Unlike insertion sort, selection sort has no `O(n)` best case - it always does `O(n²)` comparisons.

## Notes

1. **Not stable**: Selection sort is **not stable** by default. When swapping the minimum element with the current position, equal elements may change their relative order.
2. **Minimal swaps — the one reason to ever pick selection sort**: It does `O(n²)` *comparisons* like the other simple sorts, but only `O(n)` *swaps* (at most `n-1`). Every other `O(n²)` sort does up to `O(n²)` swaps. So if writes are dramatically more expensive than reads — flash memory, EEPROM, any medium where each write degrades the cell — selection sort is the right call. Outside of that niche, insertion sort wins on virtually every dimension.
3. **Not adaptive**: Performance is the same regardless of input order - no benefit from partially sorted data.
4. **In-place**: Only requires `O(1)` extra space.

## Applications

| Use Case                 | Why Selection Sort?                                  |
| ------------------------ | ---------------------------------------------------- |
| Minimizing writes        | Only `O(n)` swaps vs `O(n²)` for bubble/insertion    |
| Memory writes are costly | Flash memory, EEPROM where writes degrade the medium |
| Small datasets           | Simple implementation with predictable performance   |

**When to avoid**: When stability is required, or when the data might be partially sorted (insertion sort's `O(n)` best case would be better).

**Interview tip:** Selection sort's main advantage is its `O(n)` swaps. If asked "which sort minimizes writes?", selection sort is the answer among simple `O(n²)` sorts. However, for most practical purposes, insertion sort is preferred due to its adaptive behavior.


---

# 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://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/selectionsort.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.