replace sort

もともと、このアルゴリズムは、私のアイディアで考案し、発表したものの、
すでに、in-place merge ソートというアルゴリズムの考え方に、非常に似ていることが判明しました。
また、計算量がO(N^2)であることが推定され、特に、速い部類には入らないことも判明しました。

このまま、わかりずらいアルゴリズムの紹介のみで終わらせてしまうと、このソートに興味を示された方々に、
申し訳ないので、ここに、ソースコード(下記に示すパフォーマンステストのソース)を公開することにしました。

replaceperformancetest.zip

一昔前のPC(CPU)では、力を発揮する可能性はありますが、最近のPCでは、挿入ソートより遅いです。
その点だけ注意してください。



アルゴリズムの紹介

データの中央を基準値にします。



左右のデータを、基準値と比較していきます。
9,11,8,12,7,13・・・
左… 基準値より大きいデータがあれば、右に寄せます。
右… 基準値より小さいデータがあれば、左に寄せます。



データの移動先にあるデータの順番が狂わないように順次、左右に寄せます(安定ソートを維持するため)




以上を、左右の端に行きつくまで繰り返します。




左… 基準値より大きいデータが右に、小さいデータは左に寄ります。
右… 基準値より小さいデータが左に、大きいデータは右に寄ります。



左側の大きいデータ群と、右の小さいデータ群を入れ替えます(replace)。



基準値より小さいデータ群、大きいデータ群とに分けて再帰的に並べ替えをします。

パフォーマンス

さまざまな事情で、最新のPCを持ち合わせていないため、現実的な数値はそろっていません。
Pentium4 1.8GHzの結果















Pentium4 HT 3.0GHzの結果
※使い古しのWindows上での結果ですので、安定していませんん。あくまで、参考値


少なくとも、Pentium4系列のCPUでは、挿入ソートより、半分以下の時間で、ソートが完了する結果となりました。
安定ソートの選択肢として、insert(挿入)ソートは、あり得ません。

なお、以下は、知り合いに、協力して頂いた結果です。

Core i7

上段は、データ数です。
小数点込みで記述されているのは、時間(ms)


さすがに、最新のCPUでは、insert(挿入ソート)の方が、若干いい結果を残しています。
ただ、降順の並びを昇順に並び返す場合は、挿入ソートの比ではありません。