Rust でのマージソートの実装例です。
マージソートとは、分割統治法と呼ばれるアルゴリズムの一種です。
対象のリストを細分化していき、ソート済みリストを順にマージしていくようなソート方法です。
ソートについては既に標準ライブラリに優秀なものがあるので実用性はありません。
アルゴリズムや Rust の学習用のサンプルとして紹介します。
マージソート
プログラムサンプルです。
わかりやすさのため、途中経過も出力させるようにしています。
fn merge<T>(xs: &mut [T], mid: usize)
where
T: PartialOrd + Default + std::fmt::Debug,
{
println!("starting merge");
println!(" input : {:?}, {:?}", &xs[..mid], &xs[mid..]);
let mut lhs = vec![];
for item in &mut xs[..mid] {
lhs.push(std::mem::take(item));
}
let mut rhs = vec![];
for item in &mut xs[mid..] {
rhs.push(std::mem::take(item));
}
let mut i = 0;
let mut j = 0;
let len = xs.len();
for k in 0..len {
if mid + j == len || i < mid && lhs[i] < rhs[j] {
xs[k] = std::mem::take(&mut lhs[i]);
i += 1;
} else {
xs[k] = std::mem::take(&mut rhs[j]);
j += 1;
}
}
println!(" output: {:?}", xs);
}
fn merge_sort<T>(xs: &mut [T])
where
T: PartialOrd + Default + std::fmt::Debug,
{
if xs.len() <= 1 {
return;
}
println!("starting merge sort");
println!(" input : {:?}", xs);
let mid = xs.len() / 2;
merge_sort(&mut xs[..mid]);
merge_sort(&mut xs[mid..]);
merge(xs, mid);
println!("finished merge sort");
}
fn main() {
let mut v = vec![4, 3, 7, 9, 0, 2, 5, 6, 8, 1];
merge_sort(&mut v);
println!("sorted: {:?}", v);
}
starting merge sort
input : [4, 3, 7, 9, 0, 2, 5, 6, 8, 1]
starting merge sort
input : [4, 3, 7, 9, 0]
starting merge sort
input : [4, 3]
starting merge
input : [4], [3]
output: [3, 4]
finished merge sort
starting merge sort
input : [7, 9, 0]
starting merge sort
input : [9, 0]
starting merge
input : [9], [0]
output: [0, 9]
finished merge sort
starting merge
input : [7], [0, 9]
output: [0, 7, 9]
finished merge sort
starting merge
input : [3, 4], [0, 7, 9]
output: [0, 3, 4, 7, 9]
finished merge sort
starting merge sort
input : [2, 5, 6, 8, 1]
starting merge sort
input : [2, 5]
starting merge
input : [2], [5]
output: [2, 5]
finished merge sort
starting merge sort
input : [6, 8, 1]
starting merge sort
input : [8, 1]
starting merge
input : [8], [1]
output: [1, 8]
finished merge sort
starting merge
input : [6], [1, 8]
output: [1, 6, 8]
finished merge sort
starting merge
input : [2, 5], [1, 6, 8]
output: [1, 2, 5, 6, 8]
finished merge sort
starting merge
input : [0, 3, 4, 7, 9], [1, 2, 5, 6, 8]
output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
finished merge sort
sorted: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
コメント