-
Notifications
You must be signed in to change notification settings - Fork 8
/
selection_sort.dart
28 lines (24 loc) · 966 Bytes
/
selection_sort.dart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import '../utils/list_extension.dart';
/// Pseudocode:
/// - Store the first element as the smallest value you've seen so far.
/// - Compare this item to the next item in the array until you find a smaller number.
/// - If a smaller number is found, designate that smaller number to be the new "minimum"
/// and continue until the end of the array.
/// - If the "minimum" is not the value (index) you initially began with, swap the two values.
/// - Repeat this with the next element until the array is sorted.
///
/// Time Complexity: Best O(n²) - Worst O(n²) - Average O(n²)
/// Auxiliary Space: O(1)
void main() {
print(selectionSort([8, 4, 5, 10, 9]));
}
List<int> selectionSort(List<int> arr) {
for (int i = 0; i < arr.length; i++) {
int smallestIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[smallestIndex]) smallestIndex = j;
}
if (i != smallestIndex) arr.swap(i, smallestIndex);
}
return arr;
}