Last Update 2003/10/15
データ構造とアルゴリズム・シリーズ 3

ソート・検索
Cプログラム例と演習問題付き

浪平 博人 著
A5判 184ページ
3.5"2DD FD付き
定価2,563円(税込)
JAN9784789836753
1995年10月31日発行
[絶版2001.4.30] ソート・検索
大変恐縮ですが,こちらの商品は品切れ絶版となりました.

 アルゴリズムの宝庫といわれるソート/マージ技術を中心に,ランダム・データをあつかう応用技術,検索技術,データ抽出技術の4分野について解説しています.

目次

プロローグ

1 ソート/マージ
 1.1 選択法
 1.2 シェル・ソート(shell sort)
 1.3 ヒープ・ソート(heap sort)
 1.4 クイック・ソート(quick sort)
 補足:クイック・ソートの効率の厳密な解
 1.5 マージ・ソート(merge sort)
 1.6 バブル・ソート
 1.7 挿入によるソート(insert sort)
 1.8 カウントによるソート(sort by counting)
 1.9 ラディックス・ソート(radix sort)
 1.10 ナチュラル・マージ・ソート(natural merge sort)
 1.11 データの移動をともなわないソート
 1.12 ソート効率の上限の(n log (n))の証明
 1.13 トポロジカル・ソート(topological sort)
 1.14 マージ (merge)

2 ランダムのあつかい
 2.1 乱数について
 2.2 分布の表し方
  2.2.1 離散分布を発生させるには
  2.2.2 連続分布の発生法
  2.2.3 ノイマンの棄却法
  2.2.4 正規分布の発生
  2.2.5 分布発生の注意点:密度の考慮
 2.3 問題表現
 2.4 応用例
 2.5 演習問題

3 検索
 3.1 順次検索
 3.2 二分探索法(binary search)
  3.2.1 二分探索の手順
  3.2.2 二分探索法の解析
  3.2.3 検索データのあり場所の予測がつくときの検索回数の考察
 3.3 フィボナッチ探索
 3.4 二分木探索
  3.4.1 二分木探索の手順
  3.4.2 Bツリー検索
 3.5 ハッシュ検索
  3.5.1 チェイン法
  3.5.2 オープン・アドレス法
 3.6 データがディスクにあるとき
 3.7 範囲検索
  3.7.1 すべてのデータを順次に調べる
  3.7.2 二次インデックス
  3.7.3 グリッド法
  3.7.4 二次元ツリー法
  3.7.5 二次元ヒープ法
  3.7.6 組み合わせハッシュ法(Combinatorial Hashing)
  補足:いくつかの二次キーの一つしか指定しないときの式の算出

4 ランダムな並びからのデータ抽出法
 4.1 最大あるいは最小の要素の選択
 4.2 最大と最小の選択
 4.3 最大と2番目の選択
 4.4 ランダムな集合をpで2分割
 4.5 n個の中のm番目に小さい要素の選択
  4.5.1 分割法を用いる方法
  補足:効率解析
  4.5.2 整列二分木(heap)を利用する方法
 4.6 指定のものに近いm個の選択
 4.7 あいまいさを残した比較の考察

参考文献
INDEX
本書に掲載したおもなプログラム一覧
添付フロッピ・ディスクについて