public class Solution {
public void selectionSort(int[] arr) {
// Mutates arr so that it is sorted via selecting the minimum element and
// swapping it with the corresponding index
int min_index;
for (int i = 0; i < arr.length; i++) {
min_index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap current index with minimum element in rest of list
int temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
}
}
}
- requiring O(n^2) time to sort the list in the worst case
- The space complexity of selection sort is O(1) since we do not use any additional space during the algorithm (all operations are in-place).
- It also is not a stable sorting algorithm. For example consider the collection [4, 2, 3, 4, 1]. After the first round of selection sort, we get the array [1, 2, 3, 4, 4]. This array is sorted, but it does not preserve the ordering of equal elements.