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

計算機科学

一般にソートアルゴリズムの計算量はソート対象となるデータ数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]ple = a[p]plication

# 3文字目を比較
ap[p]le = ap[p]lication

# 4文字目を比較
app[l]e = app[l]ication

# 5文字目を比較
appl[e] < appl[i]cation

# apple < applicationとなる

といった感じで、先頭の文字から順番に比較していきイコールじゃなくなった時点で大小関係が決まる。ということは最初の文字比較でイコールでなければ直ぐに大小関係が決まる。この性質をマルチキー・クイックソートでは使っている。
普通のクイックソートではピボットとして適当な(例えば真ん中の)データを選び、そのデータより大きいグループ、小さいグループに分ける。これに対してマルチキー・クイックソートはピボットとなるデータに対して比較するときに先頭の一文字しか比較しない。その代わりピボットより小さいグループ、大きいグループ、同じグループの3つに分ける。
どういうことかというと、

change
dog
cat
apple
bag
egg

というデータをソートするときにピボットをまず選び(今回はcatにする)、ピボットの先頭一文字をキーとして小、大、同じのグループに分ける

[小]
  [b]ag
  [a]pple  
[同じ]
  [c]hange
  [c]at
[大]
  [d]og
  [e]gg

ここで、各々のグループに対して再帰的にソートをする。ただし[同じ]グループは先頭文字が同じであることが分かっているので、比較文字を2文字目にする。つまり

[小]
  [b]ag
  [a]pple  
[同じ]
  c[h]ange
  c[a]t
[大]
  [d]og
  [e]gg

で[]のついている文字で各グループがマルチキー・クイックソートをする。結果、

[小]
  [a]pple  
  [b]ag
[同じ]
  c[a]t
  c[h]ange
[大]
  [d]og
  [e]gg

というようになる。各々の比較では文字同士の比較しかしていないので文字列長Mに対して計算量がO(1)となるところがポイント。

参考:
Fast Algorithm for Sorting and Searching Strings J. L. Bentley & R. Sedgewick, 1997