Skip to content

Instantly share code, notes, and snippets.

@nebuta
Last active December 14, 2015 18:39
Show Gist options
  • Save nebuta/5130854 to your computer and use it in GitHub Desktop.
Save nebuta/5130854 to your computer and use it in GitHub Desktop.
Quick sort using generics in Rust
// 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("");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment