# Selection Sort

Source: https://wisconsin.twango.dev/fa24-cs300/u3-algorithms/sorting-and-search/sorting/selection-sort

# Selection Sort

Selection sort is a simple sorting algorithm that repeatedly selects the minimum element from an unsorted portion of the array and swaps it with the first unsorted element. The algorithm maintains two subarrays: one that is sorted and one that is unsorted. The sorted subarray is built up from left to right, while the unsorted subarray is reduced from right to left.

## Features
- [ ] Stable sorting algorithm
- [x] In-place sorting algorithm

## Implementation

### Pseudocode

```text
procedure selectionSort(A : list of sortable items)
    n = length(A)
    for i = 0 to n-2 do
        minIndex = i
        for j = i+1 to n-1 do
            if A[j] < A[minIndex] then
                minIndex = j
            end if
        end for
        swap(A[i], A[minIndex])
    end for
end procedure
```

### Java

```java
public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
```

## Runtime Analysis

The displayed selection sort scans every remaining suffix, so it makes $N(N-1)/2$ comparisons and takes $\Theta(N^2)$ time even when the input is already sorted. Its runtime is not $\Theta(N+K)$ in the inversion count $K$.

### Best and worst cases

The displayed implementation performs $N-1$ outer iterations. On iteration $i$, it scans the unsorted suffix to locate its minimum, regardless of the input order. Thus both best and worst cases take $\Theta(N^2)$ comparisons.

There is one swap per outer iteration (possibly swapping a position with itself), for $N-1$ swaps overall. Selection sort does not perform one swap per inversion.

## Source

The existing course note was retained and normalized during the merge.

Related: [[u3-algorithms/sorting-and-search/index|Topic index]].