# Selection Sort

• In selection sort, we split the sequence of elements into two parts: sorted and unsorted. At the beginning, all elements are in the unsorted part.

• We go through the sequence of elements $N$ times. Each time, we find the smallest element and append it to the end of the sorted part. We do so by swapping the smallest element with the first element in the sorted part. In other words, every time, we select the smallest element in the unsorted part; that element will be the next largest element in the sorted part.

## Complexity

• This sort is in-place and always takes $\Theta(N^2)$ time, since we have to make $N$ selections and it takes $N$ time to go through the sequence of input and make a selection.