【アルゴリズムについて】
基本情報技術者試験をきっかけに基本的なアルゴリズムを学習しました。
代表的なアルゴリズム
バブルソート（基本交換法）
隣同士のデータを順に比較して、大小関係が逆ならば交換をおこなう。
計算量：O(n**2)
挿入ソート（基本挿入法）
整列済みのデータ列にデータを挿入していくことを繰り返す。
計算量：O(n**2)
選択ソート（基本選択法）
最大値（または最小値）のデータを探して、最後のデータ（または先頭のデータ）と交換を繰り返す。
計算量：O(n**2)
2分探索法
1、データ領域を2つに分けることで範囲を絞り込み、目的のデータを探し出す。
2、データが昇順か降順に整列されている必要がある。
計算量：O(log n)
ハッシュ探索法
1、ハッシュ関数で格納位置を求めて、ほぼ1回で目的のデータを探索する。
2、データの格納効率が悪いと、領域を大きく取らないと頻繁に衝突が起こる。
3、異なるデータが同じ位置になる衝突が発生し、格納できないことがある。
※ ホームレコード：既に記憶されているレコード
※ シノニムレコード：衝突のために格納できないレコード
計算量：O(1)
線型探索法
1、配列内のデータを順々に探索キーと比較して、目的のデータを探し出す。
2、データを整列しておく必要はない。
3、データが整列済みならば、データが存在しない時に打ち切り可能。
4、最後の要素に番兵を置くことで、配列の添字チェックが不要。
計算量：O(n)
マージソート
データ列を小さく分割していき、整列して合併することで整列させる。
計算量：O(n log n)
クイックソート
基準値を決めて、基準値よりも小さいものと大きいものに振り分けて、基準値で分割されたデータ列に対しても同様に分割を繰り返して整列する。
計算量：O(n log n) 最悪 O(n**2)