マルチキー・クイックソート(multikey-quicksort)で高速に文字列ソート - EchizenBlog-Zwei

一般にソートアルゴリズムの計算量はソート対象となるデータ数NについてO(N^2)とかO(NlogN)等で評価する。数値データのソートであれば特に問題はないのだが、文字列データの場合は一回の比較に対して文字列長Mに比例する計算量O(M)がかかってしまう。例えばクイックソートであればO(NlogN)ではなくO(MNlogN)となる。よってMが非常に大きい場合はソート性能の劣化を招く。 文字列ソートに付いてはBently&Sedgewickのマルチキー・クイックソート(multikey-quicksort)という改良版クイックソートが存在する。このソート法は、ある工夫によって一回の比較を文字列長Mに依存しない形で実現している。 例えば文字列appleとapplicationの比較について考える。 # 先頭の文字を比較 [a]pple = [a]pplication # 2文字目を比較 a[p]p