《 A Engineer Den 》知的冒険の旅へ出かけよう
超最速ソートアルゴリズム解説 【概要】 Explanation for Ultra fastest sorting algorithm
概要
本書の位置づけ
本書は、ソートアルゴリズムについて記載した解説書です。主な内容を下記に示します。
- 代表的なソートのアルゴリズム
- 超最速なダイレクトマップソートのアルゴリズム
- ソート計算量と処理時間の比較
アルゴリズムとは、問題を解くための手順（解法）のことです。 同じ問題を解決するにもさまざまな方法があり、 優れた技術者は問題に適したアルゴリズムを使い分けることができます。
さて、あなたはダイレクトマップソートを知っていますか。 知らなくて当然です。私が命名したソートアルゴリズムです。
ダイレクトマップソートは、複数のソートアルゴリズムを組み合わせた超最速ソートアルゴリズムです。 多くのソートアルゴリズムは、ソートキーの大小関係を比較してソートします。 しかし、ダイレクトマップソートはダイレクトマップを作成することによりデータを直接ソートするので 高速にソートすることができます。
超最速ソートアルゴリズムは、どのくらい速いのでしょうか。 驚くことに、速さで定評のあるクイックソートを超えた最強のソートアルゴリズムです。 例えば、15000件規模のデータに対してダイレクトマップソートはクイックソートに比べて 10倍速く動作します。その仕組みについて、本書で解説します。
本書の主な対象読者
本書は、下図に示すような読者を対象としています。
- ソフトウェア技術者をめざして情報技術を学ぶ学生
- システム開発に参画するソフトウェア技術者
- 組み込み機器を開発する組み込み系技術者
ソートにはいくつかのアルゴリズムがあります。 それぞれのソートは長所と短所をあわせ持つので、アルゴリズムを勉強するための良い教材となります。 情報技術を学ぶ学生は、ぜひともソートアルゴリズムを理解してスキルを磨いてください。
また、開発現場で活躍されているソフトウェア技術者の皆さんは、 ソートアルゴリズムについて知っていますか。 ライブラリーを呼び出してソートを使う立場だとしても、ソートの仕組みについて興味はありませんか。
ソフトウェア技術者の中でも、特に組み込み系技術者に本書をお勧めします。 組み込み機器は高機能化しています。 そして、リソースに制限のある組み込みソフトウェア開発では、実行効率の良いソフトウェアが要求されます。 ときには、ソートライブラリーを呼び出すよりも目的に特化した（実行効率の良い） ソートプログラムを書いた方が良いことがあります。
本書の特徴
本書には、2つの特徴があります。
特徴の1つは、フィクション物語により擬似的にプロジェクトに参加できます。 そして、一緒に考えてください。その中で読者の皆さんに何かの気づきがあれば幸いです。
- 物語① 「超最速ソートを求めて」と「超最速ソート誕生」
- 物語② 「アルゴリズムを選べ」
もう1つの特徴は、ソートアルゴリズムを図解して手順をプログラム設計図PADで説明していることです。 図解によりアルゴリズムの理解が深まり、プログラム設計図PADで具体的な手順を理解できます。 具体的なプログラム言語（C言語、Java言語など）で説明していないので、言語仕様を知らなくても理解可能です。
プログラム設計図PADとは、プログラムの論理的な構造（プログラムロジック）を木構造のように現した 究極のプログラム設計図です。 構造化プログラミングの3つの基本制御構造（順次処理、選択処理、反復処理）の記述方法を理解すれば、 簡単に読むことができます。 PADは、２次元の図面なのでプログラムの理解にパターン認識能力を活用できます。 また、誰が書いてもプログラムの論理構造が同じであれば同じ形状の図面となり、作図の個人差を減らすことができます。
- 横軸方向：レベルの深さで複雑さ（反復、選択）を現す
- 縦軸方向：処理の大きさ（順次）を現す
詳しくは、拙著 『究極シリーズ1 － 究極のプログラム設計図 PAD解説』を参照してください。
本書について
インターネットが進化した現代は、ネットで検索することによりいろいろなソートアルゴリズムに ついて多くの情報を入手することができます。 こんな時代にいまさら「ソートアルゴリズム」について書いたのでしょうか。その理由は2つあります。
1つ目の理由は、自分が理解して整理した情報や私の経験が誰かの役に立つと考えたからです。 インターネットの情報は不確かな点があることもあります。 例えば、「データ配列の添え字のはじまりが0なのか1なのか」など、明確にしておらず 理解に苦しむことがありました。 また、本書ではソートアルゴリズムをプログラム設計図PADで示しているので、アルゴリズムの理解を助けてくれます。
2つ目の理由は、本書で取り上げる超最速ソートアルゴリズムについての情報が少ないことです。 複数のソートアルゴリズムを組み合わせたものですが、その基本となる度数ソートについて制限を強調するあまり、 非現実的だと思われています。本書により超最速ソートアルゴリズムの認知度がアップすることを期待します。
本書の目的
本書の目的は、先人の知恵であるソートアルゴリズムを理解してもらうことです。 ソートアルゴリズムは、単純な問題でありながら効率的に解くことが難しい問題であり、たくさんの種類があります。
ソフトウェア技術者は、安定性や計算量オーダーといったソートにまつわる概念について知っている必要があります。 ソートアルゴリズムの最悪時の計算量オーダーはどの程度か、 メモリーフットプリント（メモリー使用量）はどの程度かなど、考えたことはあるでしょうか。
本書を読むことにより、ソートの達人になれます。
- ソートアルゴリズムの安定性や計算量オーダーについての概念を理解できます。
- 超最速なダイレクトマップソートアルゴリズムを実現できます。
そして、目の前の問題に最適なソートアルゴリズムを選ぶことができるソフトウェア技術者をめざしてください。