Rust – マージソート

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]
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

このサイトは reCAPTCHA と Google によって保護されていますプライバシーポリシー利用規約 申し込み。

The reCAPTCHA verification period has expired. Please reload the page.

目次