# Selection Sort

## #

Overview- Time Complexity:
`O(n^2)`

, makes at most`O(n)`

swaps - Space Complexity:
`O(1)`

- In-Place
- Not stable (If implemented with a linked list, then it is stable)
- Example: [5,3,3',2,1] -> [1,3,3',2,5] -> [1,2,3',3,5] -> order of 3 and 3' has been swapped

## #

General IdeaSorts an array by *repeatedly finding the minimum* element from the unsorted part of the array and puts it at the beginning. The array maintains two subarrays in an array. The front part of the array is a subarray containing the already sorted elements.

We have an outer loop which runs from `0`

to the `len(arr) - 1`

index. In each iteration, we run an inner loop which searches for the minimum element in the remaning unsorted elements and place it at the next index available at the front subarray. Hence, the inner loop runs from index `(i+1)`

to `(len(arr) - 1)`

.

## #

Time ComplexityAs seen from the 2 loops, we have a time complexity of `O(n^2)`

.

## #

Space ComplexityWe only maintain temporary variables to know the current minimum element's index. Hence, the space complexity is constant - `O(1)`

.

## #

Implementation## #

Comparison with Bubble SortSelection sort uses a *maximum* of `n`

swaps whereas in bubble sort, we use up to `n`

swaps for each element - requires up to `n^2`

swap operations. Since write operations are memory-intensive, selection sort can be more efficient than bubble sort for large lists.