情報工学科で出る定番の課題といえば、ソートアルゴリズムの実装だ (多分) (他の大学を知らない) 。 普通の人間は愚直に実行時に配列などをソートしてしまうかもしれない。私も高校時代にこの課題が出ていたら普通に実行時にソートして喜んでいただろう。 だが、ここは大学。生半可なソートを実装して喜んでいるようではレベルが低い (ハードウェアに近いという意味ではない) 。
ヒープソートを実装して実行時間を計る課題が出たので、私はコンパイル時にstd::integer_sequenceをヒープソートした。これくらいやらなければ実行時間で他の学生に圧倒的な差をつけて勝つことはできない。ソートする整数列が長くなれば、恐ろしいほどメモリを食うが、一応メモリが無限にあればコンパイルできるようになっている。(余談だが、コンパイル時ソートを実装するのは2回目だ。以前にコンパイル時挿入ソートを実装したことがある)
そもそもヒープソートって？
ヒープソートはO(n log n)で要素をソートできるアルゴリズムだ。常に最小値または最大値がヒープのトップに来るように完全2分木を作り、末尾と先頭を入れ替えながらヒープを縮小していくと最後には綺麗に並んでいるというアレだ。アルゴリズムクイックリファレンスを読めば書いてあることなので知らない人は読んでくれ。
ヒープソートを実装する
まずヒープを作るには以下の操作が必要だ。
しかし、std::integer_sequenceの整数列のN番目とM番目の整数をスワップするのは困難を極めるか不可能なので、結果的にスワップしたように見える動作をするために、std::integer_sequenceのN番目の整数をIにする関数writeを書く。
また、そのIを求めるためにstd::integer_sequenceのN番目の整数を求める関数atも書く。
そのようにしてできたwriteとatでswapを作れば、条件を満たすときにswapしてくれるような関数swap_ifを書くと、いよいよヒープの本質を実装できるようになる。
実装したのがこちらだ。昨日書いたものだが、もうすでにどうして動いているのか分からない。もっといい書き方があれば教えてくれ！
サンプルコード
int main() { std::integer_sequence<int, 1, 3, 2, 8, 10, 0> seq; static_assert(std::is_same_v< decltype(heapsort<std::less<>>(seq)), std::integer_sequence<int, 0, 1, 2, 3, 8, 10>; >); }
