挿入ソート
Rust のアルゴリズムレシピとして挿入ソート紹介です。
サンプルコード
サンプルコードです。
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]おしまい！