CodeZine(コードジン)

特集ページ一覧

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

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

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2008/03/07 14:00

ダウンロード サンプルソース (3.4 KB)

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

目次

はじめに

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

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

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

  • LINEで送る
  • このエントリーをはてなブックマークに追加

バックナンバー

連載:japan.internet.com翻訳記事

もっと読む

著者プロフィール

  • Richard Newcombe(Richard Newcombe)

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

  • japan.internet.com(ジャパンインターネットコム)

    japan.internet.com は、1999年9月にオープンした、日本初のネットビジネス専門ニュースサイト。月間2億以上のページビューを誇る米国 Jupitermedia Corporation (Nasdaq: JUPM) のニュースサイト internet.com や EarthWeb.c...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5