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; 
    }
}