ソートの解説書

2018年12月、Amazonから『超最速ソートアルゴリズム解説』という本を出版しました。

主な内容

• ソートの基礎
• 代表的なソートアルゴリズム
• 超最速なダイレクトマップソートアルゴリズム
• ソート時間の計測結果

さて、あなたはダイレクトマップソートを知っていますか。知らなくて当然です。私が命名したソートアルゴリズムです。

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

•  「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 ダイレクトマップソート」

本書の特徴

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

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

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

フィクション物語①は、技術的な課題に直面して解決のために超最速ソートが必要となり、夢の中のアイデアから超最速ソートを実現して課題解決できたというストーリーです。

フィクション物語②は、あるプロジェクトでライブラリーのソート関数を使用しない選択をして、軽量なソートアルゴリズムで実現したというストーリーです。

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

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

究極のプログラム設計図 PAD解説

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

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

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

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

『超最速ソートアルゴリズム解説』は、究極の技シリーズ２です。

 

本の情報

• 超最速ソートアルゴリズム解説
• 2018年12月05日
• フォーマット： Kindle版
• ファイルサイズ： 23066 KB
• 出版社: 私の計算機科学研究
• 販売： Amazon Services International, Inc.

---

 

目次

はじめに
第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　ソートアルゴリズムのまとめ
おわりに
参考文献

内容紹介

アマゾンの内容紹介を下記に示します。

本書は、ソートアルゴリズムについて解説しています。

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

ソートアルゴリズムは、単純な問題でありながら効率的に解くことが
難しい問題でありたくさんの種類があります。
優れた技術者は問題に適したアルゴリズムを使い分けることができます。

計測結果のグラフ

データ件数（100～15000件）の計測結果を示します。

このグラフから、ダイレクトマップソートは圧倒的に速いということがわかります。他のソートアルゴリズムとは異なり、データ件数が増えても処理時間の増加はわずかです。また、改良型ソートは基本型ソートより速いこともわかります。

ソートの速い順

項番	種類	ソートアルゴリズム
1	究極型	ダイレクトマップソート
2	改良型	クイックソート
3	改良型	ヒープソート
4	改良型	シェルソート
5	基本型	挿入ソート
6	基本型	交換ソート
7	基本型	選択ソート

クイックソートよりも10倍速いダイレクトマップソートについて興味を持って頂いたでしょうか。

本書を読めば、その仕組みが理解できます。ソートアルゴリズムを図解して手順をプログラム設計図PADで解説しています。また、C++言語で書いたソースコードも掲載しているので実際に使うことも可能です。