Introduction
The selection sort is an in-place comparison sorting algorithm. It’s similar to bubble sort in that it works by repeatedly swapping items in a list and not very efficient on larger lists.
Code Example
func selectionSort(_ array: [Int]) -> [Int] {
var A = array
let N = array.count
for i in 0 ..< N {
var jMin = i
for j in (i + 1) ..< N {
if A[j] < A[jMin] {
jMin = j
}
}
if jMin != i {
let tmp = A[i]
A[i] = A[jMin]
A[jMin] = tmp
}
}
return A
}
Implementation
For each index:
- Set
jMin
index to the current index - For each index from
i + 1
to the end of the list:- If the element at inner index
j
is less than the element at indexjMin
, setjMin
toj
- If the element at inner index
- If
jMin
does not equali
, swap the element at the current indexi
with the element at indexjMin
Time/Space Complexity
Time complexity: O(N^2)
Space complexity: O(1) auxiliary