【基本情報・応用情報】アルゴリズムだああああ！種類・計算量・動き

# はじめに
基本情報や応用情報でのアルゴリズムを一気に復習できるような記事です！

:::note warn
データ構造やプログラミングの基礎知識については記述していないので，事前に学んでおいてください．
:::

# 探索アルゴリズム

| | 特徴                           | 平均計算量          | 補足  |
|------------|--------------------------------|-----------------|-------|
| 線形探索   | 先頭から順に探索               | $O(n)$            | ソート不要 |
| 2分探索    | 中央値と比較し範囲を半減       | $O(\log n)$        | ソート必要 |
| ハッシュ探索| キーをハッシュ関数で変換      | $O(1)$       | 衝突対策が必要  |


# 整列アルゴリズム
|    | 特徴                           | 平均計算量          | 安定   |
|--------------|-----------|-------------|----------------|
| 選択法       | 最小値を選んで順に並べる       | $O(n^{2})$          | X |
| バブルソート | 隣接要素を比較・交換           | $O(n^{2})$          | ◯ |
| 挿入法       | 要素を適切な位置に挿入         | $O(n^{2})$          | ◯ |
| シェルソート  | 挿入法の改良版，一定間隔をあけて行う   | $O(n^{1.2})$~$O(n^{1.5})$ <font color="red">※</font>|X |
| クイックソート| 分割統治法、ピボットで分割  | $O(n\log n)$ | X |
| ヒープソート | ヒープ構造を利用               | $O(n\log n)$     | X |
| マージソート | 分割統治法、部分列を比較してマージ     | $O(n\log n)$      | ◯|

<font color="red">※</font>シェルソートの最低時の計算量は$O(n^{2})$

## 選択ソート

https://codesandbox.io/embed/898hsk?view=preview&module=%2Findex.html&hidenavigation=1

## バブルソート

https://codesandbox.io/embed/6dy6sf?view=preview&module=%2Findex.html&hidenavigation=1

## 挿入ソート

https://codesandbox.io/embed/m7ngyr?view=preview&module=%2Findex.html&hidenavigation=1
 

<details><summary>画像</summary>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/c4a10a3b-c599-aa30-df0e-4053704aca0c.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/655bb99e-2fc8-b8c1-5095-2a9e575fb575.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/f56657e8-b04a-807c-0ae7-1860978edf2a.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/40779a1d-40e3-8ac2-f01c-3fb23a975de9.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/a24ea680-ca6c-6778-5028-ee67f4948cb2.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/0a85c9e8-6a35-d9bc-bd34-a1d58a12196f.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/a6125223-54d4-08bb-2fbe-833eee3c3ed6.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/78836156-e912-83cc-b1dd-882d68fe94da.png)
</details>

## シェルソート

https://codesandbox.io/embed/hyqp39?view=preview&module=%2Findex.html&hidenavigation=1

## クイックソート
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/8322ae38-eff6-c70f-b41e-a5da4009afd5.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/0cd6b00a-8a53-35f9-d11b-bf8afe319a28.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/0dfbd440-eeae-51ea-ee55-ec083263c62b.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/ce19ad75-d903-c5fb-42e1-325ce1faa59e.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/02aea544-ceb9-f249-de60-9fff210633d9.png)

## ヒープソート
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/187794bb-55a7-463f-0821-188d97118b63.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/9b2c9ed4-2f54-d599-8c57-c64b5912b0b8.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/029bb8ee-b999-50bf-ab5b-e1ef59a3a9e6.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/c6d1b383-b1f5-d2bb-7e5c-e95c7c024715.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/76c7b852-046e-d6fc-e1d5-b1c102ad1a2d.png)

## マージソート
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/3ecfe9aa-b5b6-216f-65ef-a0f286228441.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/76597fdc-c95f-14fb-168a-8e5159791715.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3748983/b77c6969-df9b-d6e4-e492-0fa837647d80.png)

# 基本情報・応用情報記事

https://qiita.com/bearl27/items/48ea517e5debbff3b2e9

https://qiita.com/bearl27/items/c08be5f2a53fd3fb7b53

https://qiita.com/bearl27/items/e63a6fb14eba0067d940

https://qiita.com/bearl27/items/f8cf339e7f966291683d

https://qiita.com/bearl27/items/849c9400ae93608331e7