はじめに
以前、素晴らしすぎる以下のサイトにて様々なアルゴリズムを学習したことがあった。
プログラミングに必要なアルゴリズムが網羅的に記載されている神サイトである。
昔、Rustの練習がてら一通りRustで実装したことがあった。
今回はこの中でもソートに着目し、5種類のソートアルゴリズムについてRustの実装コードとともに復習していきたいと思う。
ソートアルゴリズムには複数あるが、今回取り上げるのは実用的な高速ソートアルゴリズムに絞る。
バブルソートのような低性能なものは取り上げない。
クイックソート
高速ソートアルゴリズムでおそらく最も有名なアルゴリズムだと思う。
計算速度の安定性はいまいちだが、メモリ効率が良く、平均的な計算速度が非常に速い。
最悪計算量：O(n2)
平均計算量：O(n log n)
基準値の選び方を工夫することで、最悪計算量となるケースは防止できる。
平均的には最も高速と言われているので、迷ったら多分これ使えば間違いない。
// aとbのアドレスの値を交換する
fn swap<T: Clone>(A: &mut Vec<T>, a: usize, b: usize) {
let tmp = A[a].clone();
A[a] = A[b].clone();
A[b] = tmp;
}
// 配列Aの区間[l, r]をA[r]の値を基準に分割する
fn partition (A: &mut Vec<i32>, l: usize, r: usize)-> usize {
let p = l;
let mut i:i32 = (p as i32) -1;
for j in p..r {
if A[j] < A[r] {
i += 1;
swap(A, i as usize, j);
}
}
i += 1;
swap(A, i as usize, r);
i as usize
}
// 配列Aの区間[l, r]の要素をソート
pub fn quickSort(A: &mut Vec<i32>, l: usize, r: usize) {
if l < r {
let q = partition(A, l, r);
if q>0 {quickSort(A, l, q-1);}
if q<A.len() {quickSort(A, q+1, r);}
}
}
// テストする
fn main() {
let mut test = vec![5,8,6,3,2,4,4,1];
quickSort::quickSort(&mut test, 0, 7);
println!("{:?}", test);
}マージソート
クイックソートと異なり、計算速度に安定性があるが、メモリ使用量が大きいソート。
最悪計算量：O(n log n)
平均計算量：O(n log n)
安定した計算速度が求められ、かつメモリに余裕があるときにオススメ。
// 配列Aの区間[l, r)を反転する
fn reverse(A: &mut Vec<i32>, l: usize, r: usize) {
for i in l..(l + (r-l)/2) {
let j = r - (i-l) - 1;
let tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
// 配列Aの区間[l, m)の要素と区間[m, r)の要素をマージする
// それぞれの区間の要素は昇順に整列されている
fn merge(A: &mut Vec<i32>, l: usize, m: usize, r: usize) {
let mut T = A.clone();
reverse(&mut T, m, r);
let mut i = l;
let mut j = r-1;
for k in l..r {
if T[i] <= T[j] {
A[k] = T[i];
i += 1;
} else {
A[k] = T[j];
j -= 1;
}
}
}
// 配列Aの区間[l, r)に対してマージソート
pub fn mergeSort(A: &mut Vec<i32>, l: usize, r: usize) {
if l+1 < r {
let m = (l+r)/2;
mergeSort(A, l, m);
mergeSort(A, m, r);
merge(A, l, m, r);
}
}
// テストする
fn main() {
let mut test = vec![5,8,6,3,2,4,4,1];
mergeSort::mergeSort(&mut test, 0, 8);
println!("{:?}", test);
}ヒープソート
計算速度に安定性はないが、クイックソートほど不安定でない、そしてメモリ効率が非常に良いソートアルゴリズム。
ただし、並列計算できないなどの問題も存在する。
最悪計算量：O(n log n)
平均計算量：O(n log n)
組み込み開発など、とにかくメモリ使用量を抑えたいケースにオススメ。
// aとbのアドレスの値を交換する
fn swap<T: Clone>(A: &mut Vec<T>, a: usize, b: usize) {
let tmp = A[a].clone();
A[a] = A[b].clone();
A[b] = tmp;
}
// 配列Aで構築されたヒープの要素iからダウンヒープ
fn downHeap(A: &mut Vec<i32>, i: usize, N: usize) {
let l = (i+1)*2-1;
let r = (i+1)*2;
let mut largest: usize;
// 親（自分）、左の子、右の子の中で最大のノードを見つける
if l < N && A[l] > A[i] {
largest = l;
} else {
largest = i;
}
if r < N && A[r] > A[largest] {
largest = r;
}
if largest != i { // どちらかの子が最大の場合
swap(A, i, largest);
downHeap(A, largest, N);
}
}
fn heapSort(A: &mut Vec<i32>) {
// buildHeap
let mut i = ((A.len()/2) as i32) - 1;
let mut heapSize = A.len();
loop {
if i < 0 {break;}
downHeap(A, i as usize, heapSize);
i -= 1;
}
loop {
if heapSize < 2 {break;}
swap(A, 0, heapSize-1);
heapSize -= 1;
downHeap(A, 0, heapSize);
}
}
// テストする
fn main(){
let mut A = vec![5,2,3,8,1,4,3,5,9,6];
heapSort(&mut A);
println!("{:?}", A);
}シェルソート
クイックソートと同様に計算速度に安定性は全くないが、メモリ効率は非常に良いソートアルゴリズム。
計算量の算出も分割数に依存するので難しい。
O(n1.25)～O(n1.5) 程度に収まると言われているらしい。
個人的にはどういうケースで使われるか正直分かっていないアルゴリズム。
どうやら要素数が小規模(10000個以下とか?)で最も効率がよいといわれているとか。
またプログラムを見てもらえれば分かるが、再帰呼び出しなしで記載できるため、スタックの消費が一番少ないのもメリットなのかもしれない。
// 間隔gを指定した挿入ソート
fn insertionSort(A: &mut Vec<i32>, g: usize) {
for i in g..A.len() {
let t = A[i];
let mut j = (i as i32) - (g as i32);
loop {
if j < 0 {break;}
if !(A[j as usize] > t) {break;}
A[(j as usize)+g] = A[j as usize];
j -= g as i32;
}
A[(j as usize)+g] = t;
}
}
fn shellSort(A: &mut Vec<i32>) {
let interval = [5, 3, 1];
for g in &interval {
insertionSort(A, *g);
}
}
// テストする
fn main(){
let mut A = vec![5,2,3,8,1,4,3,5,9,6];
shellSort(&mut A);
println!("{:?}", A);
}計数ソート
今まで紹介してきたソートアルゴリズムと少し毛色が異なるアルゴリズム。
計算速度は安定して高速であるが、とにかくメモリを大胆に使う。
データのとりうる値の範囲によっては、メモリ不足によりこのアルゴリズムでは不可能な場合が多い。
計算量：O(n + k)
データの取りうる範囲が固定で決まっており、かつその範囲が小さいときには、最強のアルゴリズム。
要素数は多くてもかまわない、最小～最大の範囲が小さいことがポイント。
fn countingSort(A: &mut Vec<usize>) -> Vec<usize> {
let mut B = vec![0; A.len()]; // 出力用の配列
let max = (*A.iter().max().unwrap()) as usize;
let mut C = vec![0; max+1]; // 出現数保存用の配列(配列A中の最大値分)
let A_len = A.len();
for i in 0..A_len {
C[A[i]] += 1;
}
for i in 1..C.len() {
C[i] += C[i-1]
}
for i in 0..A_len {
let index = A_len-i-1;
C[A[index]] -= 1;
B[C[A[index]]] = A[index];
}
B
}
// テストする
fn main(){
let mut A = vec![5,2,3,8,1,4,3,5,9,6];
let B = countingSort(&mut A);
println!("{:?}", B);
}最後に
迷ったらクイックソートを使えば間違いなし！！
アルゴリズムについて知っておく＆自分で実装できるのはプログラミングにおいて大きな武器になる。
ソート以外にも、探索アルゴリズムや木構造アルゴルズムなど、実装したプログラムについて今後も記載していこうと思う。
コメント