ここまでに出て来たソート、サーチのプログラムは全て数値のみを対象として 操作されていたが、もちろん配列でも同じように書けるよ的な応用。 本の検索がお題。[book_seach.c] #include <stdio.h> #include <stdlib.h> #define N 5 typedef struct { char *title; char *author</stdlib.h></stdio.h>…

ニ分探索。 配列の真ん中の値と探している値を比較、それを繰り返すことでターゲットを絞って行く。 対象となる配列がソートされている必要がある。 データ量が少なかったり、ソートする時間がない場合はリニアサーチにしましょう。 [計算量] O(log N) [bina…

リニアサーチは配列の先頭から順番に調べて行って探している数字と同じであればキーを返す。 単純挿入ソートで使った方法。逐次探索、線形探索とも言う。C++標準ライブラリのfind()が相当する。 [計算量] O(N) [linear_search.c] #include <stdio.h> #include <stdlib.h> #inclu</stdlib.h></stdio.h>…

時間を使ったソート。 今年ちょっと話題になって初めてブログで見たときは、お〜なるほど〜って感じだった。 いつ使うの？と聞かれると、まだわからないとしか言えないけど、何かに使えるはず。 WindowsだったらSleepはミリ秒でスレッド実行できるようなので…

鳩の巣ソート(pigeonhole sort)なんていうのがあるらあしいですよ。 でもバケットソートの方が一般的だし、効率も良いよ。 [計算時間] O(n)高速、安定ソート [bucket_sort.c] #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int sort[N]; int</time.h></stdlib.h></stdio.h>…

何個かソートの実装例を書いてきたけど その中で最適なソートとはどれなのか。 安定ソート、不安定ソート、内部ソート、外部ソート、O(n2)、O(n log n)。 判断基準は状況によるが、処理するデータ量で考えると 大量のデータの場合はO(n log n)のクイックソー…

単純挿入ソートの改良版。単純挿入ソートでは挿入箇所をリニアサーチで探していた。 2分挿入ソートではバイナリサーチで挿入箇所を探している。 データ数が大きい場合に効率的。[計算量] O(n2) [binary_insert_sort.c] #include <stdio.h> #include <stdlib.h> #include <time.h> #defin</time.h></stdlib.h></stdio.h>…

単純挿入ソートはほとんど整列が終わっているデータに対して効率が良い。 安定ソート。内部ソート。基本挿入法ともいう。 [平均計算時間] O(n2) [最悪計算時間] O(n2) [insertion_sort.c] #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 /* データ件数 */ int </time.h></stdlib.h></stdio.h>…

コームソートは離れた要素を比較・交換して 徐々に距離（ギャップ）を縮めて行く。 荒い目から細かい目ですいていくように 髪をとかすコームが名前の由来らしい。 [計算量] なぜか本に書いてない。 wikiには『実行速度は、ほぼO(n log n)』とありますが。。…

クイックソートは元データの並びが悪いとバブルソートと同じくらい効率が悪い。 もっと確実に効率の良い方法はないかということでマージソートがありますよ、と。 クイックソートよりも最悪計算量が少ない。[マージソートの計算量] 最悪：O(N Log N) [ソース…

[クイックソートのロジック] 1.ある値を基準として、それより大きい値は後ろ、小さい値は前へ移動 2.2つのグループそれぞれでまた適当な値を基準にして大きい値は後ろ、小さい値は前へ移動 3.またそれぞれのグループで同じ様に、1-2を繰り返す 4.グループ分…

プログラマーとしてもう1STEP進むために 自分がよく理解できていない、データ構造とアルゴリズムの勉強を始めました。 実務でいつ使うの？と聞かれても納得してもらえる説明ができるようにしたいと思います。この本が良さげだったのでそれに沿って進めます。…