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

2011/12/17 PHPに打ち克って世界をより良くする『PHP Apocalipse』に行ってきました。[トピック] PHPこれからも楽しいよ ピザとビールが美味しいかった 始めて女子がいる勉強会に参加した [感想] スピーカーの皆さんの話がどれも素晴らしく バラエティーに富…

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