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

ソート手法にはいろいろなアルゴリズムがあります。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倍も速く動作することがわかりました。