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

はじめに

　アプリケーション内部では、必ずと言っていいほどリスト内の要素をソートする機会があります。この記事では、よく使われるソートアルゴリズムをいくつか紹介し、ソートを行う場合に適切なアルゴリズムを選択するためのアドバイスをします。古典的な「バブルソート」や「挿入ソート」から、複雑な「交換ソート」「スタックソート」、そして挿入ソートとスタックソートのアルゴリズムを掛け合わせた「ハイブリッドソート」までを取り上げます。各ソートアルゴリズムの長所短所もあわせて紹介していきます。

　まず、さまざまなソートアルゴリズムとその簡単な説明を見てみましょう。「安定ソートか」の列は、そのソートアルゴリズムが同一要素の並び順を保持するかどうかを示しています。

ソートアルゴリズム	方式	安定ソートか	説明
バブルソート	交換	○	基本的な2ループのソート
カクテルソート	交換	○	2方向のバブルソート
コムソート	交換	×	バブルソートの速度改良版
ノームソート	交換	○	バブルソート、挿入ソートのハイブリッド
選択ソート	挿入	×	in-placeアルゴリズムの比較ソート
挿入ソート	挿入	○	単純な比較ソート
シェルソート	挿入	×	一般的な挿入ソート
2分木ソート	挿入	○	データの2分木を構築し、2分木を使ってソート
ライブラリソート	挿入	○	間隔を空けたリスト要素間で行う挿入ソート
マージソート	マージ	○	分割してソートし、マージするアルゴリズム
in-placeマージソート	マージ	○	マージソートの空間最適化版
ヒープソート	選択	×	2段階比較型ソート
スムースソート	選択	×	ヒープソートの小型版
クイックソート	分割	×	再帰的分割とソート
イントロソート	ハイブリッド	×	クイックソートとヒープソートのハイブリッド
ペイシェンスソート	挿入	×	要素を統計的に整列
スタンドソート	選択	○	リンクリストで保存されているデータでは有効

　「ビードソート（Bead Sort）」や「ネットワークソート」のように、特定の道具が必要なものから、「ボゴソート」や「ストゥージソート（Stooge Sort）」（「Three Stooges」というコメディ番組から命名）のように、実用的でなく、実証のためだけに存在するものまで、まだまだたくさんのソートアルゴリズムや手法が存在します。

バブルソート

　バブルソートは最も古くから使われているソートアルゴリズムです。この記事で用意した基本のコードでは、2つのループを準備して、単純にリストの要素を一度に1つずつ調べ、その要素とその要素の後に続く要素とを比較し、小さい（または大きい）方の要素をリストの前方に配置します。

　このアルゴリズムを使用するには2つの方法があります。どちらも正確であり、実行時間と処理の回数はほぼ同じ結果となります。1つは「後方バブルソート」です。これは、外側のループはリストの後方から前方を参照し、内側のループはリスト前方から外側のループが指定する要素までを参照して、毎回隣り合った要素を比較し、順番が違っていればお互いの位置を交換します。

　もう1つは「前方バブルソート」です。これは外側と内側の両方のループがリストの前方から後方を参照し、外側のループが参照する要素と内側の要素が参照する要素とを比較して、順番が違っていればお互いの位置を交換するというものです。

　前方バブルソートと後方バブルソートの大きな違いは、名前からも想像がつくように、リストがソートされる方向です。ほとんどの言語では、変数の位置が少々違うだけでコードの長さは同じになるでしょう。実行時間はどちらのアルゴリズムでもほとんど同じくらいであり、たいていは、元々のリストが既にどの程度ソートされているかによって決まります。

　前方および後方バブルソートで注目すべき点は、n回目の処理が完了したときに、リストの最初または最後のn個の要素がソートされてそれぞれ正しい配置になることです。

　バブルソートを使う利点は限られていますが、一部の言語（たとえばアセンブラ）ではコンパイル後のコードが小さくなり、コードの準備やデバッグが容易であることが挙げられます。大きな欠点の1つは実行時間です。このアルゴリズムでは、リストが大きくなるにつれ、実行時間が指数関数的に増えていきます。

　では実際のコードを見てみましょう。コードリスト1は後方バブルソート、コードリスト2は前方バブルソートです。コードリスト3では、処理をスピードアップさせるためにいくつか変更を加えました。ブール値のチェックを加えることで、交換が起こらない過程があった場合は処理を停止するようにしています（交換が起こらない場合はリストのソートが完了しているので、続行する必要はありません）。ある程度ソートされているリストでは、3つのうちこのコードリストが最も速くなるでしょう。

コードリスト1

For Loop1 = 1 to
Max
For Loop2 = 0 to Max - Loop1
If List(Loop2) > List(Loop2 + 1) Then
Tmp = List(Loop2)
List(Loop2) = List(Loop2 + 1)
List(Loop2 + 1) = Tmp
End If
Next Loop2
Next Loop1

コードリスト2

For Loop1 = 0 to
Max -1
For Loop2 = Loop1 +1 to Max
If List(Loop1) > List(Loop2) Then
Tmp = List(Loop2)
List(Loop2) = List(Loop1)
List(Loop1) = Tmp
End If
Next Loop2
Next Loop1

コードリスト3

Limit = Max
Do
Switch = False
For Loop1 = 0 To (Limit - 1)
If List(Loop1) > List(Loop1 + 1) Then
Tmp = List(Loop1)
List(Loop1) = List(Loop1 + 1)
List(Loop1 + 1) = Tmp
Switch = True
Limit = Loop1
End If
Next Loop1
Loop While Switch

挿入ソート

　挿入ソートはバブルソートを一歩進めたもので、基本的には同じ原理で動作します。ループを使ってリストの最初から最後まで調査するところは変わりませんが、要素を入れ替えていくのではなく、既にソートされている部分に対して、その中の正しい位置に要素を挿入します。

　リストを降順でソートする場合、バブルソートと挿入ソートではソートにかかる時間は同程度となるでしょう。しかし、リストがある程度ソートされている場合は、挿入ソートの方が早く完了します。

　挿入ソートで興味深いのは、n回の処理が終わった時点でリストの最初のn個がソートされた状態になりますが、それらの要素が最終的に正しい位置にあるとは限らないという点です。

　挿入ソートが他のソートアルゴリズムに比べて優れているのは、たとえばユーザーが入力しているリスト項目や、外部デバイスからの入力データなど、要素をリアルタイムでソートする際に利用できることです。この目的に関しては、他のほとんどのソート方式よりもかなり高速です。

　挿入リストのコード例をコードリスト4に示します。

コードリスト4

For Loop1 = 1 To
Total
Tmp = List(Loop1)
For Loop2 = Loop1 To 1 Step -1
If List(Loop2 - 1) > Tmp Then
List(Loop2) = List(Loop2 - 1)
Else
Exit For
End If
Next Loop2
List(Loop2) = Tmp
Next Loop1

選択ソート

　選択ソートは挿入ソートとバブルソートの中間にあたり、リストの未ソート部分の中から最小値を見つけ出して先頭に配置します。選択ソートでは、要素を前方や後方に1つずつ移動するのではなく、要素の位置を交換することで正しい配置にするので、この手法を交換ソートと呼ぶこともよくあります。

　選択ソートで特筆すべき長所はあまりないのですが、配列への書き込みを行う際に比較的長いメモリアクセス時間がかかる記憶装置（たとえばEEPROMやFlashメモリなど）では、要素の交換回数が少ない選択ソートの方が、他のほとんどのソート方式よりも高速に実行できます。

　選択ソートの特徴は、n回の処理が完了した時点で要素の交換がn回だけ実行され、最初のn個の要素がソート済みの正しい位置に配置されるという点です。

　選択ソートの例をコードリスト5に示します。

コードリスト5

For Loop1 = 0 To
Total
Pos = Loop1
For Loop2 = Loop1 + 1 To Total
If List(Loop2) < List(Pos) Then
Pos = Loop2
End if
Next Loop2
If Pos <> Loop1 Then
Tmp = List(Pos)
List(Pos) = List(Loop1)
List(Loop1) = Tmp
End If
Next Loop1

ヒープソート

　ヒープソートでは二段階のソートを行います。まず予備ソートを行ってリスト内に親子ツリーを作成し、次にその親子ツリーを使ってリスト全体をソートします。

　ヒープソートを実装するにはいくつか方法があり、そのうちのいくつかのアルゴリズムでは別の配列を用意してソートを実行します。今回紹介するコードリストは、元々のリストの内部でヒープソートを行う方法を採用しており、最適化も行われています。

　始めの段階では、リストは最初の時点よりもバラバラな順序になったように見えます。しかし実際には、リスト内の最大の要素が頂点にあるような形式のソート用の親子ツリーが作成されています。次の段階では、n回の処理が完了した時点で、最後のn個の要素がソートされて正しい位置に配置されます。親子ツリーでは、処理のたびに次の最大要素を頂点に移動させるようにします。

　ヒープソートには1つ弱点があります。コードサイズが大きくなるため、コードに利用できるメモリの大きさが限られているプロジェクト（マイクロコントローラーやプログラム可能なPICなど）で使用するのは実用的でないという点です。

　コードサイズの問題はありますが、メモリの読み取り時間と書き出し時間にあまり差がないシステムでは、ヒープソートは最も高速な非再帰のソート手法として長年利用されてきました。

　コードリスト6に、実行可能なヒープソートの例を示します。

コードリスト6

For Loop1 = 1 To Total
PercolateUp Loop1
Next Loop1
For Loop1 = Total To 1 Step -1
Swap 0, Loop1
PercolateDown Loop1 - 1
Next Loop1

Sub PercolateUp(MaxLevel)
Loop2 = MaxLevel
Do Until Loop2 = 0
Parent = Loop2 ¥ 2
If List(Loop2) > List(Parent) Then
Tmp = List(Loop2)
List(Loop2) = List(Loop2 + 1)
List(Loop2 + 1) = Tmp
Loop2 = Parent
Else
Exit Do
End If
Loop

Sub PercolateDown(MaxLevel)
Loop2 = 0
Do
Child = 2 * Loop_2
If Child > MaxLevel Then Exit Do
If Child + 1 <= MaxLevel Then
If List(Child + 1) > List(Child) Then
Child = Child + 1
End If
End If
If List(Loop_2) < List(Child) Then
Tmp = List(Loop2)
List(Loop2) = List(Loop2 + 1)
List(Loop2 + 1) = Tmp
Loop_2 = Child
Else
Exit Do
End If
Loop

シェルソート

　シェルソートは挿入ソートを改良したもので、隣接する要素ではなく、いくつか間隔をおいた要素同士で比較を行い、各過程でその間隔を徐々に減らしていきます。このソートは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

著者紹介

Richard Newcombe（Richard Newcombe）

Commodore 64の時代からコンピュータに親しみ、今では優れたプログラマー、デザイナーとして活躍。30代前半で、コンピュータから離れることはめったになく、コンピュータ関連の問題ならばいつでも助力とアドバイスを惜しまない人物。最近は本サイトに関するいくつかのプロジェクトに従事。