【Rust】挿入ソート【アルゴリズム】

  • 2021年12月26日
  • 2022年8月1日
  • Rust
  • 12View
  • 0件

挿入ソート

Rust のアルゴリズムレシピとして挿入ソート紹介です。

Wikipedia 挿入ソート

サンプルコード

サンプルコードです。

i の位置の変数を一時保存するために Copy トレイトの制約を付けています。
今回は i32 型なので問題ないですが、並び替え対象の型が重い場合は、処理速度に大きく影響してしまいます。

fn insertion_sort<T>(v: &mut Vec<T>)
where
    T: PartialOrd + Copy + std::fmt::Debug,
{
    for i in 1..v.len() {
        let target = v[i];
        let mut j = i;
        while j > 0 && v[j - 1] > target {
            v[j] = v[j - 1];
            j -= 1;
        }
        v[j] = target;
        println!("i({})   : {:?}", i, v);
    }
}
fn main() {
    let mut v = vec![5, 2, 4, 6, 1, 3];
    println!("initial: {:?}", v);
    insertion_sort(&mut v);
    println!("sorted : {:?}", v);
}
❯ rustc main.rs && ./main
initial: [5, 2, 4, 6, 1, 3]
i(1)   : [2, 5, 4, 6, 1, 3]
i(2)   : [2, 4, 5, 6, 1, 3]
i(3)   : [2, 4, 5, 6, 1, 3]
i(4)   : [1, 2, 4, 5, 6, 3]
i(5)   : [1, 2, 3, 4, 5, 6]
sorted : [1, 2, 3, 4, 5, 6]

おしまい!