無料サンプル

2018年12月、Amazon『超最速ソートアルゴリズム解説』の無料サンプルについて紹介します。

本屋で本を購入するときは「はじめに」と「目次」を確認し、パラパラとめくって読みやすい本かどうかを確認してから購入します。電子書籍の場合は、紙の本と違って中身の確認ができないので、本の紹介文などにより、購入するかどうかを判断することになります。

Amazonの電子書籍は、「無料サンプル」という機能があります。この機能は、書籍の10%程度を無料でダウンロードすることができます。

超最速ソートアルゴリズム解説

超最速ソートの無料サンプル

『超最速ソートアルゴリズム解説』の無料サンプルは、「はじめに」と「目次」と「第1章の途中まで」が含まれています。

この本は、どんな内容か無料サンプルをダウンロードしてみてください。

---

以下、本書から抜粋します。

---

はじめに

本書の位置づけ

本書は、ソートアルゴリズムについて記載したもので、次のような内容を書いています。

• 代表的なソートのアルゴリズム
• 超最速なダイレクトマップソートのアルゴリズム

アルゴリズムとは、問題を解くための手順（解法）のことです。同じ問題を解決するにもさまざまな方法があり、優れた技術者は問題に適したアルゴリズムを使い分けることができます。
さて、あなたはダイレクトマップソートを知っていますか。知らなくて当然です。私が命名したソートアルゴリズムです。

超最速ソートアルゴリズム

ダイレクトマップソートは、複数のソートアルゴリズムを組み合わせた超最速ソートアルゴリズムです。多くのソートアルゴリズムは、ソートキーの大小関係を比較してソートします。しかし、ダイレクトマップソートはダイレクトマップを作成することによりデータを直接ソートするので高速にソートすることができます。

超最速ソートアルゴリズムは、どのくらい速いのでしょうか。驚くことに、速さで定評のあるクイックソートを超えた最強のソートアルゴリズムです。例えば、15000件規模のデータに対してダイレクトマップソートはクイックソートに比べて10倍速く動作します。その仕組みについて、本書で解説します。

本書の主な対象読者

本書は、図1に示すような読者を対象としています。

• ソフトウェア技術者をめざして情報技術を学ぶ学生
• システム開発に参画するソフトウェア技術者
• 組み込み機器を開発する組み込み系技術者

ソートにはいくつかのアルゴリズムがあります。それぞれのソートは長所と短所をあわせ持つので、アルゴリズムを勉強するための良い教材となります。情報技術を学ぶ学生は、ぜひともソートアルゴリズムを理解してスキルを磨いてください。

また、開発現場で活躍されているソフトウェア技術者の皆さんは、ソートアルゴリズムについて知っていますか。ライブラリーを呼び出してソートを使う立場だとしても、ソートの仕組みについて興味はありませんか。

ソフトウェア技術者の中でも、特に組み込み系技術者に本書をお勧めします。組み込み機器は高機能化しています。そして、リソースに制限のある組み込みソフトウェア開発では、実行効率の良いソフトウェアが要求されます。ときには、ソートライブラリーを呼び出すよりも目的に特化した（実行効率の良い）ソートプログラムを書いた方が良いことがあります。

本書の特徴

本書には、2つの特徴があります。

特徴の1つは、フィクション物語により擬似的にプロジェクトに参加できます。そして、一緒に考えてください。その中で読者の皆さんに何かの気づきがあれば幸いです。

• 物語① 「超最速ソートを求めて」と「超最速ソート誕生」
• 物語② 「アルゴリズムを選べ」

もう1つの特徴は、ソートアルゴリズムを図解して手順をプログラム設計図PADで説明していることです。図解によりアルゴリズムの理解が深まり、プログラム設計図PADで具体的な手順を理解できます。具体的なプログラム言語（C言語、Java言語など）で説明していないので、言語仕様を知らなくても理解可能です。

プログラム設計図PADとは、プログラムの論理的な構造（プログラムロジック）を木構造のように現した究極のプログラム設計図です。構造化プログラミングの3つの基本制御構造（順次処理、選択処理、反復処理）の記述方法を理解すれば、簡単に読むことができます。PADは、２次元の図面なのでプログラムの理解にパターン認識能力を活用できます。また、誰が書いてもプログラムの論理構造が同じであれば同じ形状の図面となり、作図の個人差を減らすことができます。

• 横軸方向：レベルの深さで複雑さ（反復、選択）を現す
• 縦軸方向：処理の大きさ（順次）を現す

詳しくは、拙著 『究極シリーズ1 － 究極のプログラム設計図 PAD解説』[1]を参照してください。

本書について

インターネットが進化した現代は、ネットで検索することによりいろいろなソートアルゴリズムについて多くの情報を入手することができます。こんな時代にいまさら「ソートアルゴリズム」について書いたのでしょうか。その理由は2つあります。

1つ目の理由は、自分が理解して整理した情報や私の経験が誰かの役に立つと考えたからです。インターネットの情報は不確かな点があることもあります。例えば、「データ配列の添え字のはじまりが0なのか1なのか」など、明確にしておらず理解に苦しむことがありました。また、本書ではソートアルゴリズムをプログラム設計図PADで示しているので、アルゴリズムの理解を助けてくれます。

2つ目の理由は、本書で取り上げる超最速ソートアルゴリズムについての情報が少ないことです。複数のソートアルゴリズムを組み合わせたものですが、その基本となる度数ソートについて制限を強調するあまり、非現実的だと思われています。本書により超最速ソートアルゴリズムの認知度がアップすることを期待します。

本書の目的

本書の目的は、先人の知恵であるソートアルゴリズムを理解してもらうことです。ソートアルゴリズムは、単純な問題でありながら効率的に解くことが難しい問題であり、たくさんの種類があります。

ソフトウェア技術者は、安定性や計算量オーダーといったソートにまつわる概念について知っている必要があります。ソートアルゴリズムの最悪時の計算量オーダーはどの程度か、メモリーフットプリント（メモリー使用量）はどの程度かなど、考えたことはあるでしょうか。

本書を読むことにより、ソートの達人になれます。
1. ソートアルゴリズムの安定性や計算量オーダーについての概念を理解できます。
2. 超最速なダイレクトマップソートアルゴリズムを実現できます。

そして、目の前の問題に最適なソートアルゴリズムを選ぶことができるソフトウェア技術者をめざしてください。

本書の構成

本書は下記に示す章から構成しています。最初から読み進めることを推奨しますが、目的によっては部分的に読むことも可能です。代表的なソートアルゴリズムについて知りたい読者は、第1章「ソートの基礎」と第3章「ソート研究」を読んでください。ダイレクトマップソートアルゴリズムについて知りたい読者は、第1章「ソートの基礎」と第5章「究極のソートとは」を読んでください。

第1章「ソートの基礎」では、ソートアルゴリズムの安定性や計算量オーダーといったソートにまつわる概念を説明します。

第2章「超最速ソートを求めて」は、フィクション物語です。技術者Yukiが直面した技術的な課題をもとに超最速なソートが必要になった理由について説明します。

第3章「ソート研究」では、代表的なソートアルゴリズムについて説明します。アルゴリズムを図解し、手順をプログラム設計図PADで示します。

第4章「超最速ソート誕生」は、フィクション物語で第2章「超最速ソートを求めて」の続編です。超最速なソートの原理について説明します。

第5章「究極のソートとは」では、ダイレクトマップソートのアルゴリズムについて説明します。アルゴリズムを図解し、手順をプログラム設計図PADで示します。さらに、C++言語のプログラムコードも掲載します。

第6章「アルゴリズムを選べ」は、フィクション物語です。課題解決に適したソートアルゴリズムを選択する重要性について説明します。

第7章「どのソートが速いか」では、ソート処理の時間計測を行い、グラフで計測結果を示して比較します。

本書で説明するソート

本書では、下記のソートアルゴリズムについて説明します。

≫ 「3.1.1 挿入ソート」
≫ 「3.1.2 選択ソート」
≫ 「3.1.3 交換ソート」
≫ 「3.2.1 シェルソート」
≫ 「3.2.2 ヒープソート」
≫ 「3.2.3 クイックソート」
≫ 「3.3.1 バケットソート」
≫ 「3.3.2 度数ソート」
≫ 「3.3.3 基数ソート」
≫ 「5.1 ダイレクトマップソート」

目次

はじめに
第1章　ソートの基礎
1.1　ソートとは
1.2　安定性とは
1.3　内部／外部ソートとは
1.4　計算量 O記法とは
1.5　in-placeとは
1.6　ソートいろいろ
第2章　超最速ソートを求めて
2.1　プロジェクト始動
2.2　設計課題の発生
2.3　探索手法の工夫
2.4　ソートの方法は
2.5　高速ソートを調査
第3章　ソート研究
3.1　基本型ソート ･･･ 挿入ソート、選択ソート、交換ソート
3.2　改良型ソート ･･･ シェルソート、ヒープソート、クイックソート
3.3　比較しないソート ･･･ バケットソート、度数ソート、基数ソート
3.4　進化するソート
第4章　超最速ソート誕生
4.1　夢の中でヒント
4.2　アイデアの原理
4.3　究極を超えたソート誕生
4.4　アイデアで実現した
第5章　究極のソートとは
5.1　ダイレクトマップソートとは
5.2　概要説明
5.3　プログラム構造
5.4　C++プログラムコード
第6章　アルゴリズムを選べ
6.1　新製品開発
6.2　たかがソート
6.3　されどソート
6.4　組み込み系では
6.5　クイックソートは速いか
6.6　ソートを選ぶ
6.7　軽量ソートで実現
第7章　どのソートが速いか
7.1　ソートの計算量
7.2　ソート時間の計測
7.3　ソート時間の結果
7.4　ソートアルゴリズムのまとめ
おわりに
参考文献