連載
» 2008年12月03日 00時00分 公開

コーディングに役立つ! アルゴリズムの基本(5):Internet Explorerよりも速くソートできたよ (1/4)

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか(編集部)

[山下寛人,オイシックス株式会社]

 第4回「Internet Explorerよりも速くソートできるかな」では、選択ソート、バブルソート、シェルソート、クイックソートを実装して、IE組み込みのソート機能よりも速くソートできるかを試しました。残念ながら、いまのところ組み込みのソートよりも速くソートできていません。しかし徐々に差は縮まっています。

 ソートのアルゴリズムは、まだまだたくさんの種類があります。代表的なものだけでもまだいくつか残っていますので、今回はこれらを実装して、IE組み込みのソート機能と速度を比較してみましょう。だんだん複雑になってきますが、頑張りましょう。

マージソート―小さく考え、大きく回答

 ある問題を解く際のアプローチに、分割統治法と呼ばれる手法があります。問題をいくつかの部分に分割し、分割された小さな問題を解き、その結果を再度まとめて全体の問題を解くというものです。

 マージソートは分割統治法の典型的な例としてよく取り上げられます。本連載でもハノイの塔やクイックソートを紹介しましたが、これらも分割統治法を用いたアルゴリズムです。分割統治法を用いたアルゴリズムは再帰とも深い関係があります。

 マージソートは次の手順でソートを行うアルゴリズムです。配列を2つの部分配列に分割します。分け方は半々です。半分に分けた配列をさらに半分に分けます。これをどんどん繰り返していくと最終的に1つ1つの要素に分解されます。

 全部分解したら今度は要素を統合(マージ)していきます。1つの要素と1つの要素を統合します。統合するときに要素同士を比較して小さい順になるようにします。要素2つの配列に統合したらほかの部分配列と統合していきます。全部統合するとソートされた状態になります。

イラストで見るマージソート

 実際の例を見てみましょう。次のような配列があったとします。

例となる配列(54836172)

 配列を分割していきます。

配列を分割する(5 4 8 3 6 1 7 2)

 分割した要素を統合していきます。左側の5と4に着目します。5と4を比較し、4の方が小さいので4を先にピックアップします。次に残った5を付け加えます。

左側の5と4を比較し、小さい4を先に、次に残った5を付け加える

 同じ要領で要素を統合していきます。

同様にほかの要素も2つずつ統合していく(4 5)(3 8)(1 6)(2 7)

 今度は2つずつの部分配列を相互に比較しながら統合していきます。まず4と3に着目します。4と3を比較し、3の方が小さいので3をピックアップします。

まず4と3を比較し、3の方が小さいので3をピックアップ(3)

 右の配列のインデックスを1つ進め、4と8を比較します。4の方が小さいので4をピックアップします。

4と8を比較し、4の方が小さいので4をピックアップ(34)

 左の配列のインデックスを1つ進め、5と8を比較します。5の方が小さいので5をピックアップします。最後に8が残るので8を付け加えます。

5と8を比較し、小さい5をピックアップ。残った8を付け加える(3458)

 あとは同じ要領でソートしながら部分配列を統合していきます。

同じ要領で残りの部分配列も統合していく(12345678)

 全部ソートできました。

 マージソートは細かい単位に区切ってソートしていくため、全体を総当たり的に比較・ソートしていくやり方より効率的にソートできます。部分に分けて処理するため、少し工夫すれば複数のコンピュータで分散処理させることもできます。

       1|2|3|4 次のページへ

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。