皆様寒くなって参りましたが如何お過ごしでしょうか？
自分は先日、自宅にて天井から食卓にゴキブリが降ってくるという恐怖体験に遭遇し、
大の大人が悲鳴を上げました。

それはさておき今回はジョークアルゴリズムのスターリンソートについてです。
ちまちま勉強しているデザインパターンの練習問題でStrategyパターンで
ソートアルゴリズムを実装してくださいと言われ、
数年前に話題になったアルゴリズムがあったなあ、、、と存在を思い出したため記事にしました。

スターリンソート（別名、粛清ソート）と呼ばれるこのアルゴリズムは、
ソ連のスターリンの大粛清になぞらえたもので、
O(N)で動作するソート(?)アルゴリズムです。

配列の要素が先頭から正しく順序通りに並んでいるかを確認し、
順序に反している要素は取り除く（粛清する）ことによって、
配列を順序付けます。
例えば次のような要素を持った配列を昇順でスターリンソートすると、
1, 2, 4, 3, 6, 8, 0, 8, 9, 5, 7
↓
1, 2, 4, 8, 8, 9
となります。

Gitリポジトリにもなっていて有志により各種言語で実装されているようです。
（海外発祥だったんですね）
GitHub – gustavo-depaula/stalin-sort

試しに自分でもC#で実装してみました。

/// <summary> スターリンソートを行います。 </summary>
public static IEnumerable<T> StalinSort<T>(IEnumerable<T> items, bool descending = false) where T : IComparable<T> {
    var prev = items.FirstOrDefault();
    var order = descending ? -1 : 1;
    return items.Where(x => order * x.CompareTo(prev) >= 0).Select(x => prev = x);
}

一時変数とLinqの併用により、すっきり書けました。

ジョークアルゴリズムですが実務で使えるタイミングを捻り出すとするなら、
例えば、正常なら右肩上がりとなる時系列データにおいて
外れ値として直前の値よりも減少したデータが記録されてしまうことがあり、
その外れ値を除去したい、などと言ったケースでしょうか。
純粋なソートとして使うことはないですが、データの正規化では使う機会があるかもしれませんね。

以上です。
皆様お身体にお気を付けてお過ごしください。