Rust:sort

sort

Overview

配列、vector型のsort関数は配列の要素をソートする

Code

• 整数の配列のソート

let mut ary = [5,2,4,3,1];
ary.sort();   // 昇順ソート(破壊的)
println!("{:?}", ary);   // [1,2,3,4,5]

let mut v = vec![5,2,4,3,1];
v.sort_by(|x, y| x.cmp(y).reverse());  // 降順ソート(破壊的)
println!("{:?}", v);    // [5,4,3,2,1]

• 浮動小数点型の配列のソート

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

let mut v:Vec<f64> = vec![1.0, 3.0, 2.0];
v.sort_by_key(|&x| Total(x));
v.reverse();
println!("{:?}", v);  // [3.0, 2.0, 1.0]  (降順ソート)

• 複数の型を持つベクター型のソート

let n:usize = read();
// [("b",3,0),("b",2,1),("a",1,2),("a",2,3)]
let mut v:Vec<(String, u32, u32)> = (0..n).map(|i| (read(), read(), i as u32)).collect();

// １番目の型を昇順, 2番目の型を降順でソートする
v.sort_by(|a,b| {
    if a.0 != b.0 {a.0.cmp(&b.0)}
    else {b.1.cmp(&a.1)}
});
// [("a",2,3),("a",1,2),("b",3,0),("b",2,1)]
println!("{:?}", v);

Detail

sort

配列を昇順ソートする

sort_by

上記のコードでは、|x,y| x.cmp(y).reverse()のクロージャを与えている。cmpメソッドは比較可能なオブジェクトを渡すと、比較して、y<xかy==xかy>xかを判定し、対応する列挙型Orderingのメンバを返す。その後、reverse()によって結果を反転している。

sort_by_key

イテレータのmapのような使い方ができる?

浮動小数点型の比較について

浮動小数点には、NANというものがあり、NANとの比較は全てfalseとなる。これにより、浮動小数点の配列にはsort()がない。そのため、ソートするには、PartialOrdトレイトを実装している型に無理やりOrdトレイトを実装するラッパstructを作る。(NANがある場合はpanicを起こす)

---

他のソートについても追記予定