Rust での挿入ソートの実装例です。
挿入ソートとは、ソート済みの配列に対して、残りの要素を挿入していくようなソート方法です。
ソートについては既に標準ライブラリに優秀なものがあるので実用性はありません。
アルゴリズムや Rust の学習用のサンプルとして紹介します。
挿入ソート
プログラムサンプルです。
わかりやすさのため、途中経過も出力させるようにしています。
fn insertion_sort<T>(xs: &mut [T])
where
T: PartialOrd + std::fmt::Debug,
{
println!("starting insertion sort");
println!("input : {:?}", xs);
println!("step 0: {:?}", &xs[0..=0]);
for i in 1..xs.len() {
for j in (0..i).rev() {
if xs[j] < xs[j + 1] {
break;
}
xs.swap(j, j + 1);
}
println!("step {}: {:?}", i, &xs[0..=i]);
}
println!("finished insertion sort");
}
fn main() {
let mut v = vec![4, 3, 7, 9, 0, 2, 5, 6, 8, 1];
insertion_sort(&mut v);
println!("sorted: {:?}", v);
}
starting insertion sort
input : [4, 3, 7, 9, 0, 2, 5, 6, 8, 1]
step 0: [4]
step 1: [3, 4]
step 2: [3, 4, 7]
step 3: [3, 4, 7, 9]
step 4: [0, 3, 4, 7, 9]
step 5: [0, 2, 3, 4, 7, 9]
step 6: [0, 2, 3, 4, 5, 7, 9]
step 7: [0, 2, 3, 4, 5, 6, 7, 9]
step 8: [0, 2, 3, 4, 5, 6, 7, 8, 9]
step 9: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
finished insertion sort
sorted: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
コメント