定本 Java プログラマのためのアルゴリズムとデータ構造

アルゴリズムの基礎が手に取るように分かる最良の著者による、アルゴリズムの定番的入門書、ここに誕生。
Java 言語の初心者/中級者を対象に、アルゴリズムとデータ構造の基礎から、各アルゴリズムの特長、Java による実装までを、平易な文章で詳細に解説。すべての Java プログラマ必読。

大ロングセラー『定本 C プログラマのためのアルゴリズムとデータ構造』の著者、近藤嘉雪の最新作です。
プログラミング上達に必須な、アルゴリズとデータ構造の基礎について、たくさんの図表と、平易な文章でわかりやすく解説しています。
取り上げるアルゴリズムは、整列 (バブルソート、選択ソート、挿入ソート、シェルソート、クイックソート、マージソート、ヒープソート、ビンソート、分布数え上げソート、奇数ソート) をはじめとして、
文字列の探索 (力まかせのアルゴリズム、KMP 法、BM 法)、バックトラック法、動的計画法など、多岐にわたっています。
紹介したすべてのアルゴリズムについて、Java によるサンプルコードを掲載しています。
すべての Java プログラマにとって、最良の一冊です。

Java でアルゴリズムとデータ構造を基礎から学び直したい人に向けた入門書が、『定本 Java プログラマのためのアルゴリズムとデータ構造』です。著者は近藤 嘉雪、版元は刊行時の社名でソフトバンククリエイティブ (後の SB クリエイティブ) で、2011 年 1 月 26 日に発売されました。版元は Java 言語の初心者と中級者を対象に、アルゴリズムとデータ構造の基礎から、各アルゴリズムの特長、Java による実装までを解説する本と案内しています。著者は『定本 C プログラマのためのアルゴリズムとデータ構造』の著者でもあり、紹介文は、たくさんの図表と平易な文章による解説と、紹介したすべてのアルゴリズムに Java のサンプルコードを載せている点を特長に挙げています。

全 6 部の構成、探索と整列と文字列の探索を柱に

目次は 6 部の構成です。「第 1 部 アルゴリズムとデータ構造の基本」で土台を固め、「第 2 部 基本的なデータ構造」「第 3 部 探索」「第 4 部 整列」「第 5 部 文字列の探索」と進み、最後が「第 6 部 いろいろなアルゴリズム」です。紹介文が挙げる題材は、整列ではバブルソート、選択ソート、挿入ソート、シェルソート、クイックソート、マージソート、ヒープソート、ビンソート、分布数え上げソートなど、文字列の探索では力まかせのアルゴリズム、KMP 法、BM 法で、さらにバックトラック法と動的計画法も取り上げています。

計算量と実装をつなぐ、アルゴリズム学習の技術背景

同じ整列でも、挿入ソートは入力がほぼ並んでいれば少ない比較で終わり、クイックソートは平均では速い一方で、基準値の選び方によっては比較の回数が入力の大きさの 2 乗に比例して増えます。こうした違いは計算量として見積もれます。紹介文は、紹介したすべてのアルゴリズムに Java のサンプルコードを載せているとしています。文字列の探索も同じで、力まかせの方法は照合に失敗するたびに 1 文字ずつずらしますが、KMP 法や BM 法は失敗した位置の情報を使ってずらす幅を大きく取り、その幅を決める表を前もってどう作るかが理解の要所になります。

動的計画法 は部分問題の結果を表に記録して同じ計算を繰り返さない設計手法で、バックトラック法は候補を順に試し、行き詰まったら一つ前の選択に戻って別の候補を試す探索の方法です。どちらも決まった手順を覚えるものではなく、問題をどう分割し、どの状態を記録するかを考える設計の型です。

版元が示す対象と、2011 年刊の前提

版元は対象を Java 言語の初心者と中級者としています。刊行は 2011 年 1 月なので、その後に Java へ加わったラムダ式や Stream API を使った書き方は前提にしていません。理論重視や演習重視の本との違いは アルゴリズム本の選び方 で扱っています。

標準ライブラリの整列を呼び出せても中身を説明できない、設計の場で計算量を根拠に選択を語れるようになりたい、という Java プログラマに向けて、本書は、主要な整列と探索、文字列の探索を Java のサンプルコードで扱います。