use std::mem::swap;
fn main() {
    let mut v = vec![5, 3, 4, 2, 1];
    bubble_sort_2(&mut v);
    println!("{:?}", v);
}

fn bubble_sort_1(v: &mut [impl Ord]) {
    if v.is_empty() {
        return;
    }
    for i in 1 .. v.len() {
        let (left, right) = v.split_at_mut(i);
        for j in 0 .. right.len() {
            if left[i - 1] > right[j] {
                swap(&mut left[i - 1], &mut right[j]);
            }
        }
    }
}

fn bubble_sort_2(v: &mut [impl Ord]) {
    for i in 0..v.len() {
        let mut min_pos = i;
        for j in i + 1..v.len() {
            if v[j] < v[min_pos] {
                min_pos = j;
            }
        }
        v[i..=min_pos].rotate_right(1);
    }
}