Visual Basicのソートアルゴリズム

VBで学ぶソートアルゴリズム

シェルソート

　シェルソートは挿入ソートを改良したもので、隣接する要素ではなく、いくつか間隔をおいた要素同士で比較を行い、各過程でその間隔を徐々に減らしていきます。このソートはDonald Shellによって開発され、1959年発行の「Communications of the ACM」という雑誌で発表されました。

　Donald Shellは元々、始めの過程でn/2の間隔を使い、各過程では前の間隔を2で割ったものを使い、最終的には挿入ソートと同じく間隔が1になるまで続けることを推奨していました。現在では、シェルソートを使う場合に最適な間隔シーケンスは、1、4、10、23、57、132、301、701であることが知られています。それ以上の間隔を必要とするリストの場合は、「次の間隔 = 間隔 * 2.3」という式を使って次の等比級数を計算することができます。

　上で説明した間隔シーケンスを使うことでシェルソートの速度が改善されますが、いくつか弱点があります。たいていの場合、次の間隔シーケンスを見つけて読み込むための命令が余分に必要になるので、コードサイズが大きくなります。さらに、要素シーケンステーブルを格納するためにメモリ使用量が少々大きくなります。

　シェルソートは、メモリのアクセス時間と書き込み時間にあまり差がないシステムでは、最も高速な非再帰のソート方式の1つです。

　コードリスト7に、Donald Shellが推奨するn/2の間隔を使用して最適化したコードを示します。

コードリスト7

Offset = Total / 2
Do While Offset > 0
Limit = Total - Offset
Do
Switch = False
For Loop1 = 0 To Limit
If List(Loop1) > List(Loop1 + Offset) Then
Tmp = List(Loop1)
List(Loop1) = List(Loop1 + Offset)
List(Loop1 + Offset) = Tmp
Switch = True
Limit = Loop1 - Offset
End If
Next Loop1
Loop While Switch
Offset = Offset / 2
Loop

クイックソート

　クイックソートは、スタックソートという名でも知られています。リスト上にランダムなピボットを設定し、ピボットを中心としてリストを分割し、一方の側にピボットより小さいすべての値を集め、もう一方の側にピボットより大きいすべての値を集めます。そして、この処理を分割されたサブリストに対して再帰的に適用します。再帰処理は、サブリストに含まれる要素が1つか2つになるまで続けます。この時点で、サブリストは正しい順序にソートされていることになります。Charles Hoareは、1960年にALGOLを基礎としたElliotシステムで使用するためにこのソートアルゴリズムを開発しました。

　このアルゴリズムは再帰的な性質を持つため、クイックソートは比較的大きいプロセッサスタックを必要とします。そして、各再帰処理で使用される多くの値を保存するため、比較的大きな量のメモリを使用します。しかし、速度が何よりも重要で、メモリを存分に利用できる場合ならば、クイックソートは驚異的に速いソートを実現します。

　クイックソートを使う上での唯一の弱点は、システムのスタックサイズが限られている場合、またはスタックを多用するプログラムで使用する場合、比較的大きなリストでは「アウトオブスタック」や「スタックオーバーフロー」エラーによって終了してしまう可能性があることです。クイックソートでは、多ければn-2回、少なければlog2(n)回の再帰処理を行います。しかし、一般的に再帰処理の許容深度は4log2nとされています。この点は常に考慮すべきであり、スタックスペースが十分でない場合は、代わりに再帰処理を必要としないソートアルゴリズムを採用する必要があるでしょう。

　クイックソートの長所は、分割してソートするという方法により、各再帰処理を新しいスレッドや別々のプロセッサで動作させるようなコーディングが可能である点です。リストが分割され、それぞれの部分が他の部分と独立しているため、それぞれの処理を平行して行うことができ、スレッド間で連携をとる必要がないため、より高速にソートが行われます。

　コードリスト8では、Charles Hoareが開発した、ピボットをランダムに選択する、元々のアルゴリズムを元にしたクイックソートを示します。

　他のすべてのアルゴリズムでも同じですが、常に改善の余地があります。何年もの間、多くのクイックソートの改良型が生み出されましたが、そのほとんどはわずかな速度の改善が見られただけです。しかし、ソート時間がほぼ半分となる改良型があります。

　コードリスト9では、その改良型を示します。このアルゴリズムは処理中に末尾再帰呼び出しを1つ作成しますが、残念ながらマルチスレッドは許可されていません。しかし、前処理と後処理によって、十分速いソートが実行できます。

コードリスト8

Sub StackSort(Low, High)
If Low < High Then
If High - Low = 1 Then
If List(Low) > List(High) Then
Tmp = List(Low)
List(Low) = List(High)
List(High) = Tmp
End If
Else
RndIndex = Int(Low + 1 + (Rnd() * (High - Low - 2)))
Tmp = List(High)
List(High) = List(RndIndex)
List(RndIndex) = Tmp
Part = List(High)
Do
TmpL = Low
TmpH = High
Do While (TmpL < TmpH) And (List(TmpL) <= Part)
TmpL = TmpL + 1
Loop
Do While (TmpH > TmpL) And List(TmpH) >= Part)
TmpH = TmpH - 1
Loop
If TmpL < TmpH Then
Tmp = List(TmpL)
List(TmpL) = List(TmpH)
List(TmpH) = Tmp
End If
Loop While TmpL < TmpH
Tmp = List(TmpL)
List(TmpL) = List(High)
List(High) = Tmp
StackSort Low, TmpL - 1
StackSort TmpL + 1, High
End If
End If

コードリスト9

Sub
QuickSort(Low, Up)
While Up > Low
Loop1 = Low
Loop2 = Up
Part = List(Low)
While Loop1 < Loop2
While List(Loop2) > Part
Loop2 = Loop2 - 1
Wend
List(Loop1) = List(Loop2)
While (Loop1 < Loop2) And List(Loop1) <= Part
Loop1 = Loop1 + 1
Wend
List(Loop2) = List(Loop1)
Wend
List(Loop1) = Part
QuickSort Low, Loop1 - 1
Low = Loop1 + 1
Wend