【Rust】挿入ソート

挿入ソートも n * (n – 1) / 2 の計算量になる。
対象データを一時領域に確保しておき、値が大きかどうかを判定して、大きい場合は入れ替えるという作業を繰り返す。
usizeは-にならないため、 j== 0の時は判定しています。

fn main() {
    let mut data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13];

    for i in 1..data.len() {
        let temp = data[i];
        let mut j = i - 1;
  
        while (j >= 0) && (data[j] > temp) {
            data[j + 1] = data[j];
            if j == 0 {
                break;
            }
            j -= 1;
        }
        if j == 0 && (data[j] > temp) {
            data[0] = temp;
        } else {
            data[j + 1] = temp;
        }
        println!("sorted data:{:?}", data);
    }
    println!("sorted data:{:?}", data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.52s
Running `target/debug/rust`
sorted data:[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sorted data:[4, 6, 15, 2, 8, 5, 11, 9, 7, 13]
sorted data:[2, 4, 6, 15, 8, 5, 11, 9, 7, 13]
sorted data:[2, 4, 6, 8, 15, 5, 11, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 15, 11, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 11, 15, 9, 7, 13]
sorted data:[2, 4, 5, 6, 8, 9, 11, 15, 7, 13]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 15, 13]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
sorted data:[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

途中経過を見ると美しいが、これも計算量が多くなる模様。