Selection Sort
Key Idea
Each outer loop selects the smallest element and places it in the beginning.
Code
public void selectionSort(int[] arr) {
int smallest;
for (int i = 0; i < arr.length - 1; i++) {
smallest = selectSmallest(arr, i);
swap(arr, smallest, i);
}
}
// return the index of the smallest element in that subarray
private int selectSmallest(int arr[], int start) {
int minimum = start;
for (int i = start + 1; i < arr.length; i++) {
if (arr[i] < arr[minimum]) {
minimum = i;
}
}
return minimum;
}
Time Complexity
The analysis is similar to bubble sort. O(n^2).
Last updated