Quicksort in Rust

Rust

注釈：以下のコードはRust 0.5で書かれたもので、最新のバージョン（1.3）では全くコンパイルできない

Rustでクイックソート。Genericsを使っていて、配列の要素がOrdトレイトのインスタンスならば何でもソートできる。

quicksort.rs

use cmp::Ord;

fn partition<T: Ord>(ns: &mut [T], l: uint, r: uint) -> uint {
  let p = &mut ns[l];
  let mut i = l + 1;
  for uint::range(l+1,r) |j| {
    if ns[j] < *p {
      ns[i] <-> ns[j];
      i += 1;
    }
  }
  ns[l] <-> ns[i-1];
  i - 1
}

fn quicksort<T: Ord>(ns: &mut [T], l: uint, r: uint) -> uint {
  if r-l <= 1{
    0
  }else{
    let p = partition(ns,l,r);
    let a = quicksort(ns,l,p);
    let b = quicksort(ns,p+1,r);
    a + b + (r-l-1)
  }
}

fn main(){
  let nums: ~mut [int] = vec::to_mut(~[1,3,2,5,10,4,6,7,8,9]);
  print_vector(nums);
  io::println("");
  quicksort(nums,0,vec::len(nums));
  print_vector(nums);
}

fn print_vector(ns: &[int]) {
  for ns.each |&n| {
    io::print(fmt!("%d ",n));
  }
  io::println("");
}

スワップの演算子 <-> は言語のプリミティブとして用意されている。最初コンパイルを通すまで、Mutable/immutableの配列の受け渡しやポインタの種類の不一致でコンパイラに結構怒られ、いろいろいじくって合わせたが結構難しい。Haskeller的メンタリティーから言えば、コンパイルが厳しいということはそれだけ実行時に安全だと期待できる。

新規登録して、もっと便利にQiitaを使ってみよう