Sorting in Code
Sorting
Selection Sort
Selection sort is when we iterate each position and try and get our smallest value each time. E.g. in python
def selection_sort(array):
m = len(array)
for i in range(m - 1):
# Assume the current index (i) has the minimum value
min_index = i
# Find the minimum element in the remaining unsorted part
for j in range(i + 1, m):
if array[j] < array[min_index]:
min_index = j
# Swap the found minimum element with the first element of the unsorted part
array[i], array[min_index] = array[min_index], array[i]
Looking at the code there are two for loops meaning this is O(n²)
And here it is in rust
fn selection_sort(numbers: &mut Vec<i32>) {
for i in 0..numbers.len() {
let mut min_index = i;
for j in i..numbers.len() {
if numbers[j] < numbers[min_index] {
min_index = j;
}
}
numbers.swap(i, min_index);
}
}
Bubble Sort
This was the first sort I did 40 years ago. Here in rust. Again this is this is O(n²)
fn bubble_sort(numbers: &mut Vec<i32>) {
for i in 0..numbers.len() {
for j in 0..numbers.len() - 1 {
if numbers[j] > numbers[j + 1] {
numbers.swap(j, j + 1);
}
}
}
}
There were improvements made in the course to the original answer where they identified code repeated even thought we knew the data was already sorted. A clear reason not to just cut and paste.
fn bubble_sort(numbers: &mut Vec<i32>) {
let mut sorted = true;
for i in 0..numbers.len() {
sorted = true;
for j in 0..numbers.len() - 1 {
if numbers[j] > numbers[j + 1] {
numbers.swap(j, j + 1);
sorted = false;
}
}
}
if sorted {
break;
}
}