闇の力を駆使すればO(1)でスターリンソートなぞ容易いものよ

そう...Templateならね！！！

スターリンソートとは

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる

— やんぎん (@4116You) July 28, 2019

なんと$O(N)$でソートが終了するという、実行速度にハートフルでピースフルなアルゴリズムです。
ピースフルなのでソート順に並んでいない要素は粛清されます。

公式リポジトリ

スターリンソートは素晴らしいアルゴリズムなので、なんと公式リポジトリが存在します。
素敵
https://github.com/gustavo-depaula/stalin-sort

先駆者達

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell
計算量O(n)で噂のスターリンソートを実装してみた
[Rust] スターリンソートと PartialOrd
rubyでスターリンソートをやってみた（ブロック渡しも可能）
スターリンソート in perl
話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した
Pythonワンライナーでスターリンソート

更に高みへ

コンパイルタイムで計算すれば$O(1)$なのでは？と思ったので実装しました。

実装

若干余計なコードが含まれているかもしれない

#include <iostream>
#include <utility>

template<int...Seq>
using seq = std::integer_sequence<int, Seq...>;

template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01;


template <class Result>
struct stalin_sort_stopper {
	using result = Result;
};
// nextを展開するwrap
template<class Result, int CompTarget, int...Next>
constexpr stalin_sort_impl_01<Result, sizeof...(Next), CompTarget, Next...> stalin_sort_next_wrapper(seq<CompTarget,Next...>) {};
template<class Result>
constexpr stalin_sort_stopper<Result> stalin_sort_next_wrapper(seq<>){};


//seqへinsertする
template<int I, int... Seq>
constexpr seq<Seq...,I> insert(seq<Seq...>) {};

// Target粛清
template<class Result, bool Comp, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01 {
	using next = seq<CompTarget, Rest...>;
	using result = Result;
};

// Target同胞
template<class Result, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01<Result, true, CompTarget, InsertTarget, Rest...> {
	using next = seq<CompTarget, Rest...>;
	using result = decltype(insert<InsertTarget>(Result{}));
};

template<class Result, class Next>
struct stalin_sort_holder_detail : decltype(stalin_sort_next_wrapper<Result>(Next{})) {};
template<class Holder>
struct stalin_sort_holder : stalin_sort_holder_detail<typename Holder::result,typename Holder::next> {};

template<class Result, int A, int B, int ...Rest>
struct stalin_sort_impl_comp_insert : 
	stalin_sort_holder<
		stalin_sort_impl_comp_insert_01<Result, (A <= B), (A <= B) ? B:A, B, Rest...>
	> {};

// result, target, rest_size, rest
// rest_size > 1なら targetとrestのheadを比較
// rest_size = 0ならresult展開して終了
template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01 : stalin_sort_impl_comp_insert<Result, Target, Rest...> {};

template<class Result, int Target, int ...Rest>
struct stalin_sort_impl_01<Result, 0u, Target, Rest...> {
	using result = Result;
};

template<int Target, int...Rest>
struct stalin_sort : stalin_sort_impl_01<seq<Target>, sizeof...(Rest), Target, Rest...> {};

// printer
template<int Head, int ...Tail>
void print_impl() {
	auto& out = std::cout;
	out << Head;
	using expander = int[];
	(void)expander{0, (void(out << ',' << Tail), 0)...};
	out << std::endl;
}


template<int ...Seq>
void print(seq<Seq...>) {
	print_impl<Seq...>();
}



int main() {
	print(typename stalin_sort<0>::result{}); // => 0
	print(typename stalin_sort<2,3>::result{});
	print(typename stalin_sort<2,1,3>::result{}); // => 2,3
	print(typename stalin_sort<1,2,3,4,5>::result{}); // => 1,2,3,4,5
	print(typename stalin_sort<2,1,3,3,2,5,6>::result{}); // => 2,3,3,5,6
	return 0;
}

解説っぽいもの

stalin_sort（エントリ関数）

template<int Target, int...Rest>
struct stalin_sort : stalin_sort_impl_01<seq<Target>, sizeof...(Rest), Target, Rest...> {};

まず、ここで入力された数列に対してTargetとRestに分解し、先頭の数値をseq<Target>へ保持します。sizeof...(Rest)によって残りの数列の長さを取得しています。

stalin_sort_impl_01

// result, target, rest_size, rest
// rest_size > 1なら targetとrestのheadを比較
// rest_size = 0ならresult展開して終了
template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01 : stalin_sort_impl_comp_insert<Result, Target, Rest...> {};
 
template<class Result, int Target, int ...Rest>
struct stalin_sort_impl_01<Result, 0u, Target, Rest...> {
	using result = Result;
};

stalin_sort_impl_01はreduceと同じような仕組みでresultにデータを蓄積していく手法を取っています。また、ここでRestの長さが0の場合にResultを返しています。

比較と粛清

// Target粛清
template<class Result, bool Comp, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01 {
	using next = seq<CompTarget, Rest...>;
	using result = Result;
};
 
// Target同胞
template<class Result, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01<Result, true, CompTarget, InsertTarget, Rest...> {
	using next = seq<CompTarget, Rest...>;
	using result = decltype(insert<InsertTarget>(Result{}));
};

template<class Result, class Next>
struct stalin_sort_holder_detail : decltype(stalin_sort_next_wrapper<Result>(Next{})) {};
template<class Holder>
struct stalin_sort_holder : stalin_sort_holder_detail<typename Holder::result,typename Holder::next> {};

template<class Result, int A, int B, int ...Rest>
struct stalin_sort_impl_comp_insert : 
	stalin_sort_holder<
		stalin_sort_impl_comp_insert_01<Result, (A <= B), (A <= B) ? B:A, B, Rest...>
	> {};

比較関数の本体です。(A <= B) ? B : Aがキモで、比較対象の更新をここで行なっています。
stalin_sort_impl_comp_insert_01で**(A <= B)による場合分けを行い、粛清したりしなかったりしています。
その結果をstalin_sort_holderとstalin_sort_holder_detailで取り出してstalin_sort_next_wrapperに渡します。
stalin_sort_next_wrapperはseq型になっているNextを展開し、CompTargetとNext...**のパラメーターパックを取り出すためのトリックです。この中でstalin_sort_impl_01が呼び出されることによって再帰的に計算を実行できています。

Seqを展開して標準出力に表示する

// printer
template<int Head, int ...Tail>
void print_impl() {
	auto& out = std::cout;
	out << Head;
	using expander = int[];
	(void)expander{0, (void(out << ',' << Tail), 0)...};
	out << std::endl;
}
 
 
template<int ...Seq>
void print(seq<Seq...>) {
	print_impl<Seq...>();
}

seq型を展開してprintする為のイディオムです。int[]の直接初期化構文内でパラメーター展開が利用できる事を使用して出力文を書き、コンマ演算子によって0に評価した後、(void)で何もなかったことにしています。

結果

int main() {
	print(typename stalin_sort<0>::result{}); // => 0
	print(typename stalin_sort<2,3>::result{});
	print(typename stalin_sort<2,1,3>::result{}); // => 2,3
	print(typename stalin_sort<1,2,3,4,5>::result{}); // => 1,2,3,4,5
	print(typename stalin_sort<2,1,3,3,2,5,6>::result{}); // => 2,3,3,5,6
	return 0;
}

以上を用いることで無事$O(1)$でスターリンソートを実装することができました。

めでたしめでたし

Online Demo

PR

折角なのでPR出しておきました。レギュレーション違反だから通るかどうか心配だな
https://github.com/gustavo-depaula/stalin-sort/pull/35

二度とやりたくない

追記1: 無事Mergeされました

や　っ　た　ぜ

追記2: 闇の同胞

• モダンな闇の力でスターリンソート！

  闇の同胞がC++17でよりスマートに書いてくださいました！（PRを出すのです……）