・有限のデータの中から、目的のデータを探す事
例：配列を走査して、目的の値を見つける
int iarray[10]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0};
0 1 2 3 4 5 6 7 8 9 ← index
キー値６を探せ！ indexの０からたどっていき、index7でキー値6を見つけたよ。
探索結果 ＝＞ iarray[7]が６に一致
性能（場合による）＝ 探索の速さ ＝ 処理の少なさ ⇐ 繰り返し数と比較数
ハッシュ法 ＞ 二分探索 ＞ 線形探索
データ形式：
配列：
配列＝＞同じ型のデータが複数あり、名前とインデックスで表現されたもの (double a[5]; => a[0] ～a[4]がdouble型で用意される）
レコード：
（キー項目）| （キーに付属した情報)
商品番号 | 商品名 | 単価
A001 | ハンバーガー | 200
A003 | チーズバーガー | 260 <= レコード形式（固定幅データ）
A005 | エッグサンド | 240
A007 | アイスコーヒー | 120
… | … | …
表＝テーブル(table)
・データ列（レコード、配列など）を先頭から順番に一個ずつ逐次、キー値（探索値）と比較して、 見つかるまで走査する方法
例題６－１
レコード
index| CarNo | CarName
0 | 1003 | "MarkⅡ"
1 | 1012 | "Chaser"
2 | 1053 | "Mr2"
3 | 1031 | "Rx-7"
4 | 1021 | "Minica"
5 | 1075 | "Legacy"
・CarNoで探して、車種名を出力する探索
変数として必要なもの → indexをたどるためのカウンタ変数 i
探すCarNoを保存しておく変数（キー値＝探索キー）var=1053
例）探索キーが１０５３で入力されたとき（P９２） 結果"Mr2"と表示される
if(var == 1053 && i<=最大データ数)
{
carNameを出力
}
・番兵法
if(var == 1024 && i<=最大データ数（Ｎ）) //アルゴリズムとしては、比較回数は２
{
carNameを出力
}
・データが見つからなかったときは最大データ数Ｎｘ２回の比較が必要
・最大データ数を１増やしておいて、最後に番兵を配置することで、比較回数を減らす作戦（ストラテジー）
index| CarNo | CarName
0 | 1003 | "MarkⅡ"
1 | 1012 | "Chaser"
2 | 1053 | "Mr2"
3 | 1024 | "Rx-7"
4 | 1021 | "Minica"
5 | 1075 | "Legacy"
… | … | …
N | XXX | "XXXXX"
N+1 | 1024 | -------
＝探索キー＝番兵
while(var != 1024) //アルゴリズムとしては、比較回数は１
{
carNameを出力
i = i + 1;
}
if(i==N+1){
データが見つからなかったときの処理;
}else{
データが見つかった時の処理
}
//(N+1) x 1 Nは０以上
ーーーーーーーーーーー【複合条件】ーーーーーーーーーーーーーーーーーーーーーーーーーー
・比較の時に複数の条件を組み合わせて真偽値を決める
i>0
i<=10
・ＡＮＤ → 且つ 両方同時に成り立てば真 C/C++では && (shift+6)
例：ｘが０以上６未満（数学だと０≦ｘ＜６）
ｘが０以上 且つ ６未満 x >= 0 && x < 6
・ＯＲ → 又は どちらかが成り立てば真 C/C++では || (shift+\(バックスペースの左）)
例：xが０以下 または、ｘが６より大きい（数学だと x ≦ 0, x ＞ 6）
x <= 0 || x > 6
・Ｎｏｔ → ～でない 条件を否定して真偽を逆転させる
not(x>=0) ＝＞ x < 0と同値 C/C++では !(x >= 0) と書く
!(x >= 0) == (x < 0)
剰余の演算子 % → x%3 xを３で割ったあまりが結果
割り切れる＝余りが０
変数int ｘにおいて、
・３で割り切れて、かつ５で割り切れる x%3==0 && x%5==0
・３で割り切れる、正ではない整数 !(x>=0) && x%3==0
x<0 && x%3==0
・３でも、５でも割り切れない !(x%3==0) && !(x%5==0)
このような複合条件が１度に書けるようになる。
ーーーーーーーーーーー【複合条件】ーーーーーーーーーーーーーーーーーーーーーーーーーーー
順次
選択（条件分岐）
繰り返し（継続条件、終了条件） 2%3==0 -> 2%3=2 -> 2==0? -> false 条件＝真偽値です。
・相手にしているデータ→整列済みデータ(昇順化、降順に並んだデータ） サンプルデータ[3, 5, 6, 8, 12, 34, 36, 37, 45, 49] 0 1 2 3 4 5 6 7 8 9 例） ・探索キー＝３７ サンプルデータ[3, 5, 6, 8, 12, 34, 36, 37, 45, 49] 0 1 2 3 4 5 6 7 8 9 サンプルデータ[ 34, 36, 37, 45, 49] 5 6 7 8 9 サンプルデータ[ 34, 36, 37, 45, 49] 5 6 7 8 9 サンプルデータ[ 34, 36, 37 ] 5 6 7 サンプルデータ[ 34, 36, 37 ] 5 6 7 サンプルデータ[ 37 ] 37発見 7
int iarray[10]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0};
0 1 2 3 4 5 6 7 8 9 ← index
キー値６を探せ！ indexの０からたどっていき、index7でキー値6を見つけたよ。
探索結果 ＝＞ iarray[7]が６に一致
配列数を num
探索値を key
int i = 0;
while( i < num ) ①条件その１：配列数はオーバーしていないか？
{
iarray[i]はkeyですか？ ②条件その２：keyは見つかったか？
Yes： indexを出力（返す：ループを抜ける）
No： 何もしない(i = i+1)
}
複合条件で一緒に書いてみよう！
while(i<num && iarray[i] != key )
{
i = i+1;(i++;)
}
if(i == num)
Yes: keyは見つかってない
No: return( i ); //iでkeyが見つかってループ抜けてる
これをさらに、スタイリッシュに書く！
int iarray[10]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0};
0 1 2 3 4 5 6 7 8 9 ← index
int temp[11]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0, ???};
0 1 2 3 4 5 6 7 8 9 10 ← index
keyが見つかる場合
keyを一番最後に代入します。
int temp[11]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0, 6};
0 1 2 3 4 5 6 7 8 9 10 ← index
while(iarray[i] != 6) //配列オーバーのチェックがいらなくなる 比較回数１/２
{
i = i+1;(i++;)
}
if(i == num)
Yes: keyは見つかってない
No: return( i ); //7でkeyが見つかってループ抜けてる
keyが見つかる場合
keyを一番最後に代入します。
int temp[11]={2, 5, 8, 1, 4, 7, 3, 1, 9, 0, 6};
0 1 2 3 4 5 6 7 8 9 10 ← index
while(iarray[i] != 6) //配列オーバーのチェックがいらなくなる 比較回数１/２
{
i = i+1;(i++;)
}
if(i == num)
Yes: keyは見つかってない //i==num (10)でループを抜けている
No: return( i );
一般化
keyを一番最後に代入します。
int temp[11]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0, key}; temp[num-1]←key 番兵
0 1 2 3 4 5 6 7 8 9 10 ← index
while(iarray[i] != key) //配列オーバーのチェックがいらなくなる 比較回数１/２
{
i = i+1;(i++;)
}
if(i == num)
Yes: keyは見つかってない
No: return( i ); //iでkeyが見つかってループ抜けてる
「配列の最後に、番兵を置いておくことで線形探索の配列オーバーのチェックが必要なくなり、
各ステップでの比較が半分になる」
アルゴリズムの評価
・早い（いろんな意味で速い、早い）
・少ないプログラムステップで終わる（CPUの動作ステップが少ない）
・効率がいい（同じ動きをする者の中で一番コストが低い）
・メモリの使用量が少ない
・一般性が高い（いつでも同じように動く）
・いつどんな状況でやっても安定して同じような結果を返す
・理解のしやすさ（美しさ）
・誰でも実装できそうか？簡便で賢い方法か？
ビッグオー記法で大体のアルゴリズムの効率を表す
for(i=0 i<l;i++)
for(j=0;j<m;j++)
for(k=0;k<n;k++)
//なんやかんや
l=m=n=N N*N*N N^3の繰り返しの回数 O(N^3) Nの３乗に支配されてアルゴリズムが動く
for(i=0 i<l;i++)
for(j=0;j<m;j++)
//なんだかんだ
N*N O(N^2) オーダN二乗のアルゴリズム
for(j=0;j<m;j++)
N回 O(N)のアルゴリズム
ハッシュ法
１回 O(1)のアルゴリズム
基本情報技術者H14秋 午前 問１３
A[i](i=1～n) n個の要素があるよ
（１）A[] ={XX,XX,XX,XX ... XX}
i=1～nまでを探索して、最小値の要素を探す
min = A[0]
min_i = 1;
for(i=1;i<=n;i++)
if(min < A[i]) ←比較
{
min = A[i];
min_i = i;
}
swap(A[1], A[min_i]);
O(N)×O(N) = O(N^2)
①５回比較
|1 2 3 4 5 index
|3 4 6 1 2 要素数5
min_i = 4
min = 1
swap(1,4)
②４回比較
1 |2 3 4 5 index
1 |4 6 3 2
min_i = 5
min = 2
swap(2,5) indexで交換
③３回
1 2 |3 4 5 index
1 2 |6 3 4
min_i = 4
min = 3
swap(3,4)
④２回
1 2 3 |4 5 index
1 2 3 |6 4
min_i = 5
min = 4
swap(4,5)
1 2 3 4 |5 index
1 2 3 4 |6
バブルソート
1 2 3 4 5 index
3 4 6 1 2 要素数5
3 4 1 6 2 要素数5
3 4 1 2 |6 要素数5
3 4 1 2 |6 要素数5
3 1 4 2 |6 要素数5
3 1 4 2 |6 要素数5
3 1 2 |4 6 要素数5
3 1 2 |4 6 要素数5
1 3 2 |4 6 要素数5
1 2 |3 4 6 要素数5
1 2 3 4 6 最良 O(n)
6 4 3 2 1 最悪 O(n^2) ←平均計算量
選択ソート
最悪 最良 平均 O(n^2)←平均計算量
挿入ソート
書いてみて
最悪の場合
最良の場合
平均 O(n^2)←平均計算量
マージソート
最悪、最良、平均 O(n・log(n))
クイックソート
最悪 O(n^2) ソート済みに近い状態が遅い
最良 O(nlogn)
平均 O(nlogn)
logの底は2又は１０
https://qiita.com/kokorinosoba/items/1c7400ca6c740fe9f1ee
https://karippu.com/stability_sort_algorithm/