Rustでソートアルゴリズム (2)挿入ソート・シェルソート

## 概要
要素が少ない時はほぼ最速となる挿入ソートを実装し、その発展形であるシェルソートを実装する。

## 前提条件
[前回](http://qiita.com/chalharu/items/c18f98635f1c52d5c662)と同様にRustのバージョンは1.19.0とします。

```shell
% rustc --version
rustc 1.19.0 (0ade33941 2017-07-17)
```

## 挿入ソート
[Wikipediaでの説明](https://ja.wikipedia.org/wiki/挿入ソート, "挿入ソート - Wikipedia")

```rust:InsertSort
fn sort<T: PartialOrd>(source: &mut [T]) {
    for i in 1..source.len() {
        let mut j = i;
        while 0 < j && source[j - 1] > source[j] {
            source.swap(j - 1, j);
            j -= 1;
        }
    }
}
```

とりあえず書いて見たが、非常に遅い。
少し改善を図ってみる。

```rust:InsertSort改良
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    for i in 1..source.len() {
        let mut j = i;
        let t = source[j].clone();
        while 0 < j && source[j - 1] > t {
            source[j] = source[j - 1].clone();
            j -= 1;
        }
        source[j] = t;
    }
}
```

Clone制約を要求するようになったが、倍ぐらいに高速化した。
なおrustでは、Index bounds checkが存在する為、配列アクセスの方法によってはかなり遅くなる。
[Rust の Index bounds check の性能影響を調べてみた - gifnksmの雑多なメモ](http://gifnksm.hatenablog.jp/entry/2016/06/01/010152)
今回のソースでは、範囲外アクセスは考えられないことから、Index bounds checkを外す為、unsafeを使って高速化してみる。

```rust:InsertSort改良+unsafe
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    for i in 1..source.len() {
        let mut j = i;
        unsafe {
            let t = (*source.get_unchecked(j)).clone();
            while 0 < j && *source.get_unchecked(j - 1) > t {
                *source.get_unchecked_mut(j) = (*source.get_unchecked(j - 1)).clone();
                j -= 1;
            }
            *source.get_unchecked_mut(j) = t;
        }
    }
}
```

最初と比較して３倍ぐらいに高速化した。
なお、次のサイトの通り、std::ptr::copy_nonoverlappingを使うと、速度が変わらずClone制約を取り払うことができる
[Rustで挿入ソート + 強制move outで高速化 - 簡潔なQ](http://qnighy.hatenablog.com/entry/2017/04/06/070000)

```rust:InsertSort改良+unsafe改良版
fn sort<T: PartialOrd>(source: &mut [T]) {
    let len = source.len();
    let ptr = source.as_mut_ptr();
    for i in 1..len {
        unsafe {
            let mut j = i;
            let mut t: T = mem::uninitialized();
            ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1);
            while 0 < j && *(ptr.offset((j - 1) as isize)) > t {
                ptr::copy_nonoverlapping(
                    ptr.offset((j - 1) as isize),
                    ptr.offset(j as isize),
                    1,
                );
                j -= 1;
            }
            ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1);
            mem::forget(t);
        }
    }
}
```
ただ、unsafeの多用はRustの安全性を損なうこととなる為、注意が必要である。

## シェルソート
挿入ソートを改良したシェルソートといったものがある。
[Wikipediaでの説明](https://ja.wikipedia.org/wiki/シェルソート, "シェルソート - Wikipedia")

```rust:ShellSort
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    let mut h = 1;
    while h < source.len() / 9 {
        h = h * 3 + 1;
    }

    while h > 0 {
        for i in h..source.len() {
            let mut j = i;
            let t = source[j].clone();
            while h <= j && source[j - h] > t {
                source[j] = source[j - h].clone();
                j -= h;
            }
            source[j] = t;
        }
        h /= 3;
    }
}
```

前回作成したコムソートより若干高速だった。