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

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

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

はじめに

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

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

ソートアルゴリズム	方式	安定ソートか	説明
バブルソート	交換	○	基本的な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