ソートアルゴリズム研究

ソート研究

ソート研究

ソートアルゴリズム いろいろ

ソート手法にはいろいろなアルゴリズムがあります。2019年5月、ソートアルゴリズム別の処理時間を比較しました。

ソートアルゴリズムは、挿入法、選択法、交換法に分類できます。それぞれのソート手法には、基本型と改良型があります。

  • 基本型 : 実行効率は悪いが考え方が簡単
  • 改良型 : 実行効率は良いが考え方が複雑

 

項番 分類 基本型 改良型
1 挿入法 挿入ソート シェルソート
2 選択法 選択ソート ヒープソート
3 交換法 交換ソート クイックソート

表に示したソートアルゴリズムの詳細は、拙著の「超最速ソートアルゴリズム解説」を参照してください。

ソートの計算量

ソート手法は、アルゴリズムのデータ比較回数により「どのくらい計算に時間がかかるか」という計算量O(オーダー)で実行効率を比較することができます。

  • 基本型のソート手法の計算量は、O(N×N)でデータ数Nの二乗に比例します。
  • 改良型のソート手法の計算量は、O(N×logN)でデータ数NとNの対数の積に比例します。

O(N×N)、O(N×logN)、O(N)のグラフを下記に示します。

ソートの計算量

ソートの計算量

データ件数が増えるごとに、それぞれの計算量の格差は開いていきます。

究極のソートアルゴリズム

データの大小比較によるソートでは、計算量O(N×logN)が限界だと考えられています。では、この限界を超える手法はないのでしょうか?

超最速ソートアルゴリズム解説」で紹介したダイレクトマップソートは、計算量O(N)のソートです。

15000件規模のデータで、速さで定評のあるクイックソートよりも10倍も速く動作するので驚きです。

ダイレクトマップソートは、究極を超えたソートアルゴリズムです。

時間計測

本を執筆したときは、15000規模のデータで計測しました。もっとデータ量が増加した場合はどうなのだろうと今回計測しました。

16bitソートキーで、データ量を5000件~55000件まで5000件刻みでソート処理時間を計測しました。

シェルソート、ヒープソート、クイックソート、ダイレクトマップソートについて比較しました。

計測に使用したPC情報を次に示します。

  • PC : Intel Core i7-3770 CPU @ 3.40GHz / 16GB RAM
  • OS : Windows 10 Pro Version 1803
  • C++ : Microsoft Visual Studio Community 2017 Version 15.8.1 (Release Mode 最適化/O2)

計測時間の絶対値は、PCのスペックにより変化しますので、データ量増加による処理時間の増加に注目してください。

ソート手法 15000件 35000件 55000件
ダイレクトマップ 167ms 402ms 712ms
クイックソート 1,926ms 4,789ms 7,477ms
ヒープソート 2,522ms 5,858ms 10,288ms
シェルソート 3,862ms 10,356ms 16,834ms
ソートの計測結果

ソートの計測結果

グラフの縦軸は計測時間で単位は[ms]で、横軸はデータ件数です。

シェルソート、ヒープソート、クイックソートは、データ量の増加に伴い計算量も徐々に増加していきます。それに対して、ダイレクトマップソートはデータ数Nに比例して計算量は増えますが、その増加はわずかです。

データ量55000件規模で、ダイレクトマップソートは712msです。クイックソートは7,477ms、
ヒープソートは10,288ms、シェルソートは16,834msです。

シェルソート > ヒープソート > クイックソート > ダイレクトマップソート

ダイレクトマップソートは、クイックソートに比べて10倍速く動作しました。

まとめ

シェルソート、ヒープソート、クイックソート、ダイレクトマップソートについて処理時間を計測して比較しました。

ダイレクトマップソートは、速さで定評のあるクイックソートよりも10倍も速く動作することがわかりました。