UNIXプラットフォームのC言語の勉強を始めようと思う。 この本を教科書にします。Unix/Linuxプログラミング理論と実践作者: Bruce Molay,長尾高弘出版社/メーカー: アスキー・メディアワークス発売日: 2008/04/21メディア: 大型本購入: 9人 クリック: 280回…

非適応型の整列アルゴリズムを調べるための最も簡単なモデルは比較交換の操作だけでデータにアクセスする抽象マシーンである。このようなマシーンを整列ネットワークという。整列ネットワークは比較器を構成要素としてそれらを線で結合したもの。整列ネット…

シャッフル（完全シャッフルと完全逆シャッフル）と比較交換走査だけを使った整列法をBatcher奇遇マージソートという。 完全シャッフル ファイルの第一要素、次に後半部分の第一要素、次に前半部分の第二要素、後半部分の第二要素というように並べ、前半部分…

バイトを右から左へ調べていく整列法。安定性を優先する場合に使用する？プログラム10.4 LSD基数整列法 右から左に動いてワードの中のバイトに関してキー添字計数法を実現したもの。キー添字計数法は必ず安定であるように実現する。Rが2の時（byteswordとbit…

三分岐基数クイックソート クイックソートによりキーの先頭の文字でファイルを整列し、キーの残りについてこの方法を再帰的に適用する。この方法は文字列の整列に対して標準のクイックソートやMSD基数整列法より優れている。プログラム10.3 三分岐クイックソ…

2進クイックソートにおいて1ビットを分割に使うことは、キーを基数2の数（2進数）として扱い、最高位のビットから調べていくということである。上位のバイトから調べることによって基数Rの数を整列するにはR個の部分に配列を分割する必要がある。このように…

整列法において、キーを分解して一定の大きさ（バイト）の列と見なすという抽象に話を移す。2進数はビットの列であり、文字列は文字の列であり、10進数は数字の列であるというように見る。一時に数の一部分を扱う事に基づく整列法は基数整列法（radixsort）…

今までの順位キュー、ヒープのプログラムでは操作join, delete_the_maximum, insertが最悪の場合に能率よく実行できない。順序のないリストではjoin, insertは速いが、delete_the_maximumは遅い。順序のあるリストではdelete_the_maximumは速いがjoinとinser…

順位キュー キューを使用する多くの場合、必ずしも完全に整列している必要もなく、すべてのレコードが同時に必要になることもない。また、レコードの中で最大要素を処理し次にもっと多くのレコードを集めてその中で現時点での最大要素を処理することが多い。…

順位キューの中のレコードが配列に入っている場合、順位キューのルーチンは配列の添字を通して項目を参照するのが良い。プログラム9.11 添字の順位キュー ADTインターフェース クライアントは二つのレコードを比較するlessルーチンを用意する。less(i, j)の…

プログラム9.8 一級順位キュー ADT インターフェース typedef struct pq* PQ; typedef struct PQnode* PQlink; PQ PQinit(); int PQempty(PQ); PQlink PQinsert(PQ, Item); Item PQdelmax(PQ); void PQchange(PQ, PQlink, Item); void PQdelete(PQ, PQlink);…

プログラム9.7 ヒープソート forループでヒープを作成する。ヒープ作成後、whileループで配列の最後の要素と最大の要素を交換してヒープが空になるまでヒープを作り直す。これでa[1]が最小要素、a[N]が最大要素の配列が出来上がる。 void heapsort_pq(Item a…

マージソートで使う補助配列のための作業領域を使う代わりにリンクの為の作業領域を使う。マージソートはリンクリストと相性が良い。プログラム8.6 リンクリストの併合 link merge(link a, link b) { struct node head; link c = &head; while ((a != NULL) …

どの再帰的プログラムにもそれに対応する非再帰的プログラムがある。 大きさ15のファイルに対するマージソートを例にする。 以下の用に要素を併合していく。 1-1 1-1 1-1 1-1 1-1 1-1 1-1 2-2 2-2 2-2 2-1 4-4 4-3 8-71-1併合を７回、2-2併合を3回、2-1併合…

マージそーとのアルゴリズムを改良する 一つ目の改良はクイックソートで行ったように小さい部分ファイルには挿入ソートを使うようにする。 二つ目の改良は補助配列のコピーに使う時間を省く。二つのルーチンを用意して一方が入力をaux、出力をaに、他方が入…

全部理解できては無いけどマージソートの性質を以下に残しておきます。 性質1 マージソートは要素N個の任意のファイルを約NlogN回の比較で整列する。（説明) 併合のプログラムでは(N/2)-(N/2)併合がN回の比較で実行できる。整列全体の比較回数は以下の標準的…

マージソートはクイックソートに相補的であり、二つの再帰呼び出しの後で併合操作を行うもの。良い点として最悪の場合でもNlogNに比例する時間で整列できることがある。欠点として、Nに比例する作業領域が必要になる。2ウェイ併合 入力ファイルが二つありそ…

整列に関する重要な問題として必ずしも完全に整列する必要がなく、数の集合の中の中央値を求める事がある。 これにクイックソートの分割を利用する。 クイックソートは配列a[l],....,a[r]を並び変えてある整数iを返すとともにa[l],...,a[i-1]がiより小さいか…

重複したキーがある場合の対処として、ファイルを三つに分割し分割要素と比べ部分ファイルをそれぞれ小さい、等しい、大きいキーだけからなるようにする。 vより小さい vに等しい vより大きい l j i rこの実装法として以下の方法がある 左の部分ファイル内で…

改良1：挿入整列法 小さい部分ファイルに対してはクイックソートではなく挿入ソートを使用する。下のMはパラメータで大体5から25を選ぶ。この範囲内のMであればM＝1を選ぶより10%くらい実行時間が少なくなる。 if (r-l <= M) insertion(a, l, r); もしくは以…

クイックソートにスタックを使用する場合、スタックの大きさはlogNに比例する。しかし縮退する場合はスタックがNに比例して大きくなりうる。既に整列済みのファイルの場合最悪のケースになる。この問題を解決するため、二つの部分ファイルの大きさをチェック…

ここからクイックソートのお勉強 クイックソートの特徴 スタック領域を少ししか使わないのでその場で整列できる N個の項目の整列に平均約NlogN回の操作しか必要でない 内側のループが極端に短く書けること 安定でなく最悪の場合約N2乗に比例する回数の操作が…

キーの特別な性質を利用して、能率を上げるアルゴリズム。 0と1の異なるキーがある場合を考える。例えば0は合格、1は不合格など。やり方としては0の個数を数えて、次のパスで入力を見て作業用配列bに入力aから配布する。 まずcnt[0]に0を入れる。ファイルの…