# Rustでソートアルゴリズム (3)選択ソート・ヒープソート

More than 1 year has passed since last update.

## 前提条件

```% rustc --version
```

## 選択ソート

Wikipediaでの説明

SelectionSort
```fn sort<T: PartialOrd>(source: &mut [T]) {
for i in 0..(source.len() - 1) {
let mut k = i;
for j in (i + 1)..source.len() {
if source[j] < source[k] {
k = j;
}
}
if k != i {
source.swap(i, k);
}
}
}
```

## ヒープソート

Wikipediaでの説明

どんなデータでも\$O(n \log n)\$のオーダーとなる。

HeapSort
```fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
let ls = source.len() >> 1;
let mut i = ls;
while i > 0 {
i -= 1;
let j = source[i].clone();
let mut n = i;
while n < ls {
let mut l1 = (n << 1) + 1;
if l1 + 1 < source.len() && source[l1] < source[l1 + 1] {
l1 += 1;
}
if j >= source[l1] {
break;
}
source[n] = source[l1].clone();
n = l1;
}
source[n] = j;
}
let mut i = source.len();
while i > 0 {
i -= 1;
let j = source[i].clone();
source[i] = source[0].clone();

let mut n = 0;
let mut leaf = 1;
while leaf < i {
if leaf + 1 < i && source[leaf] < source[leaf + 1] {
leaf += 1;
}
if j >= source[leaf] {
break;
}
source[n] = source[leaf].clone();
n = leaf;
leaf = (n << 1) + 1;
}
source[n] = j;
}
}
```

この時点で標準ソートより速かったりする。

unsafeを使って高速化してみる

HeapSort(Unsafe)
```fn sort<T: PartialOrd>(source: &mut [T]) {
let ls = source.len() >> 1;
let mut i = ls;
let ptr = source.as_mut_ptr();
let len = source.len();
while i > 0 {
i -= 1;
let mut n = i;
unsafe {
let mut j: T = mem::uninitialized();
ptr::copy_nonoverlapping(ptr.offset(i as isize), &mut j, 1);
while n < ls {
let mut l1 = (n << 1) + 1;
if l1 + 1 < len &&
*(ptr.offset(l1 as isize)) < *(ptr.offset((l1 + 1) as isize))
{
l1 += 1;
}
if j >= *(ptr.offset(l1 as isize)) {
break;
}
ptr::copy_nonoverlapping(ptr.offset(l1 as isize), ptr.offset(n as isize), 1);
n = l1;
}
ptr::copy_nonoverlapping(&j, ptr.offset(n as isize), 1);
mem::forget(j);
}
}
let mut i = len;
while i > 0 {
i -= 1;
unsafe {
let mut j: T = mem::uninitialized();
ptr::copy_nonoverlapping(ptr.offset(i as isize), &mut j, 1);
ptr::copy_nonoverlapping(ptr, ptr.offset(i as isize), 1);
let mut n = 0;
let mut leaf = 1;
while leaf < i {
if leaf + 1 < i &&
*(ptr.offset(leaf as isize)) < *(ptr.offset((leaf + 1) as isize))
{
leaf += 1;
}
if j >= *(ptr.offset(leaf as isize)) {
break;
}
ptr::copy_nonoverlapping(ptr.offset(leaf as isize), ptr.offset(n as isize), 1);
n = leaf;
leaf = (n << 1) + 1;
}
ptr::copy_nonoverlapping(&j, ptr.offset(n as isize), 1);
mem::forget(j);
}
}
}
```

ここまでやっても標準ソートと比較してn≧4096の領域で１割ほど遅い。
なおn<4096の領域では全く歯が立たない。