Rust を使ってソートアルゴリズムを実装してみる
Rust を使ってソートアルゴリズムを実装してみます。バブルソート、洗濯ソート、挿入ソートをそれぞれ実装します。
Rust はクセが強いので、結構苦労しましたが以下を学びました。
- 配列要素の交換は
swap()を使う - Clone を実装する型は
clone()を使える - Copy を実装すると型は配列の要素をそのまま交換できる
- 10..1 みたいな範囲指定はできないので (1..10).rev() を使う
バブルソート
バブルソートは隣り合った要素を交換していくソートアルゴリズムです。とても遅いソートです。
とりあえず比較できる型の配列に対してソートできるようにしたいので、PartialOrd を実装する型を対象にした関数を定義します。配列内の要素を書き換えるので可変参照で渡します。
fn bubble_sort<T: PartialOrd>(array: &mut [T]) {
// ...
}
あとはループを入れ子にして、比較＆交換をしていきますが、交換がうまく行きません。よくある次のような書き方はうまくいきません。
let tmp = array[1];
array[1] = array[0];
array[0] = tmp;
交換途中にarray[1]の参照が複数の要素に適応されるから所有権的にNGみたいです。Copy可能な型(i32などのプリミティブ型)であれば、こういう方法も可能ですが。
ではどうするか、swap() を使います。swap関数は、インデックスを指定することで指定要素を交換してくれる便利な関数です。これを使えば要素の交換が1行でかけます。
ということで実装したバブルソートの全体は以下のようになります。
fn bubble_sort<T: PartialOrd>(array: &mut [T]) {
// 後ろから順に前に交換していく
for i in 0..array.len() - 1 {
for j in (i + 1..array.len()).rev() {
if array[j - 1] > array[j] {
array.swap(j, j - 1);
}
}
}
}
動きとしては一番うしろから順番に前に降りてくる感じです。Rustだと 10..0 みたいな逆順の連番を生成できないっぽいので rev() でひっくり返しています。あんまりスマートではないですが、動きとしてはOKです。
選択ソート
選択ソートは未整列部分から最小値を取り出して並べる方法です。
fn selection_sort<T: PartialOrd>(array: &mut [T]) {
// 小さい値から順に選択し、並べる
let mut min = 0;
for i in 0..array.len() - 1 {
for j in i..array.len() {
if array[min] > array[j] {
min = j;
}
}
array.swap(i, min);
}
}
これは良さげです。最小値のインデックスを保持しつつ、未整列部分の先頭と入れ替えています。
挿入ソート
整列済の部分に対して、適切な位置に要素を挿入して並べる方法です。
fn insertion_sort<T: PartialOrd>(array: &mut [T]) {
for i in 1..array.len() {
for j in (1..i + 1).rev() {
if array[j - 1] > array[j] {
array.swap(j, j - 1)
} else {
break;
}
}
}
}
上の方法は適切な位置に要素を挿入するまでに交換しながら移動させていますが、これは遅いです。挿入対象のデータを退避しておいて、隣の要素をずらしながら挿入位置に値をセットするほうが速く処理できます。
ですが、どうも要素を対比しておいて値をずらすということができないので困りました。例えば 40, 20 という2要素の配列をソートする際に、以下のような手順を踏みたいのです。
- 挿入対象の “20” を変数に退避。
- “40” を後ろにずらす ->
40, 40 - 挿入位置に対比していた ”20″ を入れる ->
20, 40
整数値だと値のコピーができるのでこの方法ができるのですが、コピーできないオブジェクトだと 2. のときに同じ参照を持つ別の要素が存在することになり、コンパイラに怒られてしまいます。
対処法は、Copy を実装する型制約を追加するか、Clone を実装する型制約で値を取り出すときに都度 Clone するかです。どちらにせよ swap より速く動くみたいです。
以下それぞれのパターンの実装です。少しコードを変えています。
Copy を使う場合
fn insertion_sort_2<T: PartialOrd + Copy>(array: &mut [T]) {
for i in 1..array.len() {
let tmp = array[i];
if array[i - 1] > tmp {
let mut j = i;
while 0 < j && array[j - 1] > tmp {
array[j] = array[j - 1];
j -= 1;
}
array[j] = tmp;
}
}
}
Clone を使う場合
fn insertion_sort_3<T: PartialOrd + Clone>(array: &mut [T]) {
for i in 1..array.len() {
let tmp = array[i].clone();
if array[i - 1] > tmp {
let mut j = i;
while 0 < j && array[j - 1] > tmp {
array[j] = array[j - 1].clone();
j -= 1;
}
array[j] = tmp;
}
}
}
以上。
