fn main() {
    let mut liste_de_nombres = vec![34, 50, 25, 100, 65];
    let resultat = tri_insertion(&mut liste_de_nombres);
    println!("La liste de nombres triée est {:?}", resultat);

    let mut liste_de_caracteres = vec!['y', 'm', 'a', 'q'];
    let resultat = tri_insertion(&mut liste_de_caracteres);
    println!("La liste de caractères triée est {:?}", resultat);

    let mut liste_de_chaines = vec!["Xen", "Alia", "Zorro", "Nur"];
    let resultat = tri_insertion(&mut liste_de_chaines);
    println!("La liste de chaînes triée est {:?}", resultat);

    let mut liste_un = vec![1];
    let resultat = tri_insertion(&mut liste_un);
    println!("La liste de un caractère triée est {:?}", resultat);

    let mut liste_zero : Vec<i32> = vec![];
    let resultat = tri_insertion(&mut liste_zero);
    println!("La liste de zéro caractère triée est {:?}", resultat);
}

fn tri_insertion<T: Clone + std::cmp::PartialOrd>(liste: &mut [T])
						  -> &[T] {
    if liste.len() < 2 {return liste};
    for i in 1..liste.len() {
        let mut j = 0;
        while j < i && &liste[j] < &liste[i] {
            j += 1;
        }
        let mut k = i;
        let s = liste[i].clone();
        while k > j {
            liste[k] = liste[k - 1].clone();
            k -= 1;
        }
        liste[j] = s;
    }
    liste
}