スターリンソートというソーティングアルゴリズムをさまざまな言語で実装することが流行っているらしい。
- [Rust] スターリンソートと PartialOrd - Qiita
- rubyでスターリンソートをやってみた（ブロック渡しも可能） - Qiita
- 計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita
- 計算量O(n)で噂のスターリンソートを実装してみた - Qiita
- 話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した - Qiita
こんなソーティング方法もあるのかと目からうろこだった。
それならば，あまり知られていないアベソートを Ruby と Rust で実装してみよう，と思ったのがこの記事。
アベソートとは
計算機科学でいうソートとは，言うまでもなく，何らかの観点で大小比較が可能な要素の列が与えられたとき，その大小比較に従って昇順（または降順）に並んだ要素の列を返すことである。
ソーティングアルゴリズムの速さは，要素の数 $n$ に対して計算量がどのように増えるか，という指標で比べられる。
例えば $n$ が十分大きいとき計算量が $n^2$ に比例するなら $O(n^2)$ と書き，「$n^2$ のオーダーだ」などと言う。
アベソートはスターリンソートと同じく $O(n)$ である。これを「線形時間で実行できる」と表現する。ソーティングとしては（特殊なものを除き）最も速い部類である。
アベソートは $O(n)$ のアルゴリズムの中でも，（同じ要素数で比較して）実行時間の短いことで知られている。
そのうえ，原理が極めて単純で理解しやすく，コードが簡潔に書けるため，新しく学んだ言語で Hello, World! の次に挑戦する課題として適している。
Ruby による実装
シンプルなので，とくに説明は要るまい。
module Enumerable
def abe_sort
max = first
map{ |v| (v > max) ? (max = v) : max }
end
end
ary = [2, 6, 4, 5, 7, 10, 13, 12]
p ary, ary.abe_sort
Rust による実装
Rust は完全に素人なので，何か気づいた点があれば教えてほしい。
fn abe_sort<T: PartialOrd + Copy>(vec: &Vec<T>) -> Vec<T> {
let mut max = vec[0];
vec.into_iter()
.map(|v| {
if v > &max {
max = *v;
*v
} else {
max
}
})
.collect()
}
fn main() {
let ary = vec![2, 6, 4, 5, 7, 10, 13, 12];
println!("{:?}", ary);
println!("{:?}", abe_sort(&ary));
}
名称の由来
アベソートの名称の由来は諸説あってはっきりしない。
しかし，いずれも，政治権力の強引な行使が行われた故事にちなむようだ。
コードを見て分かるとおり，アベソートは，要素が昇順に並んでいない場合に，要素を並べ替えるのではなく，昇順になるよう要素自身を操作する，という考え方に基づいている。そこで，権力者が自らの主張に沿うよう事実をねじ曲げた政治史上の出来事にちなんで名付けられたというのだ。
一説では，ある言葉の意味について宰相が議会で誤った内容の発言をし，のちに内閣がその発言を正当化する内容の閣議決定を行った珍事による，とする。
別の説では，打ち出した経済政策の効果が経済統計上，思わしく出ていないために，統計の手法自体を変更して上向きを演出した事件による，とする1。
アベソートの挙動から言えば後者の説に説得力があるようだが，どうだろう。
いずれにせよアベが何を指しているのかは定かでない。日本人の人名のようだが，アベと発音する姓を持つ政治権力者は奈良時代から現代に至るまで少なくはない（漢字表記もさまざま）。また，米国（あるいは英国）の政治家，Abraham の愛称である Abe にちなむ Abe sort を日本人が誤ってアベソートと読んだものが広がった，という説もある。ドイツ人名 Abbe にちなむという説もあるが根拠に乏しいようだ。
参考文献を示したかったが，どうも民明書房の本で読んだような気がする，という程度しか思い出せない。
-
国内総生産の算出方法の変更は国際基準に合わせたため，と説明されていたが，実際にはさまざまな変更が同時に行われており，しかも細目が公表されていないため，どのような操作が行われたのか今もって解明されていないという。 ↩