電算 - 最速のソート

「ソートの本」を読んで「最速のソート」は要素数Nが小さいときは本当に速い気がしたので勢いで作ってみました。なんだかNの数だけ草生えるのでwを付けてます。

ダウンロード

ファイル名	説明
example.cpp	N=4の使用例
fastest_sort_w4.h	最速のソートwwww
fastest_sort_w8.h	最速のソートwwwwwwww
LICENSE.txt	ライセンス
README.txt	概要と略歴
test_fastest_sort_w4.cpp	N=4のテスト
test_fastest_sort_w8.cpp	N=8のテスト

GenerateFastestSortw_1.1.0.zip (4KB)

ファイル名	説明
generate_fastest_sort_wn.cpp	最速のソートを自動生成するプログラム
LICENSE.txt	ライセンス
README.txt	概要と略歴

ライセンス

商用・非商用を問わず使えるようにMITライセンスで公開します。
ジョークソートの仲間ですし、保証は何もありません。

詳細はzipファイル内のLICENSE.txtを参照してください。

アルゴリズム

アルゴリズムは以下のとおりで単純です。

なるべく少ない比較回数で、どの並び順であるかを特定する。
最小限の交換(swap)でソート順に並べ替える。

使い方

example.cppがN=4のときの使用例になっています。

#include "fastest_sort_w4.h"

テンプレートで実装したのでヘッダファイルをインクルードすれば準備完了です。

array<int, 4> data{ 3, 1, 4, 2 };
fsw4::sort(data.begin(), data.end());

昇順なら、引数にbegin()やend()などのイテレータを渡して範囲を指定するだけでソートできます。

fsw4::sort(data.begin(), data.end(), greater<>{})

降順など他の並びにするときは、第3引数で比較方法を変えます。

int a = 3;
int b = 1;
int c = 4;
int d = 2;
fsw4::sort4(a, b, c, d);

コンテナに入っていないバラバラの変数でも引数に渡すだけでソートできるようにしてみました。引数2個のsort2()と、引数3個のsort3()もあります。

VisualStudio 2015とg++ 5.4.0でコンパイルして動作確認しました。コンパイル方法はg++だと以下のコマンドになります。

$ g++ -std=c++14 example.cpp

使用例の実行結果は以下のとおりです。

$ a.out data = { 3, 1, 4, 2 } # ソート前のデータ（配列） fsw4::sort() asc data = { 1, 2, 3, 4 } # sort()で昇順にソートした結果 fsw4::sort() desc data = { 4, 3, 2, 1 } # sort()降順にソートした結果 a = 3, b = 1, c = 4, d = 2 # ソート前のデータ（バラバラの変数） fsw4::sort4() asc a = 1, b = 2, c = 3, d = 4 # sort4()で昇順にソートした結果 fsw4::sort4() desc a = 4, b = 3, c = 2, d = 1 # sort4()で降順にソートした結果

最速のソートの限界？！

N=8は手で入力するわけにいかず、最速のソートを自動生成するプログラムを作って苦労の末に完成しました。

つまり、どういうことかと言うと、ちょいと定数を変えればN=10でも20でも余裕ということです（やったね）

しかしながら、N=8のコンパイル結果は、internal compiler errorとかもうね…

メモリ2GBの貧弱な仮想マシン上だったから、メモリ4GBにしたらコンパイルできたもんねっ！！！