# Chapter16-9 「データを整列させるアルゴリズム」

## 8/10(火)

###### tags:`基本情報技術`

さつき：
> 箱の中に入っているデータを、規則ただしく並べかえる。

*　　基本交換法（バブルソート）
*　　隣接するデータの大小を比較。
*　　必要に応じて入れ替えることで全体を整列させる。
*　　最後までいったら、また先頭にもどって比較していく。
*　　比較の必要がなくなったら終了〜。
*　　基本選択法（選択ソート）
*　　データの中から最小値（または最大値）のデータを取り出して、先頭のデータと交換していく。
*　　基本挿入法（挿入ソート）
*　　対象のデータ列を「整列済みのもの」「未整列のもの」に分ける。
*　　この未整列の側から、データをひとつずつ整列済みの列の「適切な位置」に挿入して、全体を整列させていく。
> 図がわかりよい。
> 未整列からひとつデータを持ってきて、整列済みのデータの中に、どんと入れていく。
> 整列済みが4と16,未整列に10があったら、10を4と16の間に挿入するなど。
*　　より高速な整列アルゴリズム
*　　　シェルソート...[シェルソートとは](https://medium-company.com/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88/)
*　　　クイックソート...[クイックソートとは](https://medium-company.com/%e3%82%af%e3%82%a4%e3%83%83%e3%82%af%e3%82%bd%e3%83%bc%e3%83%88/)
*　　　ヒープソート...[ヒープソートとは](https://medium-company.com/%e3%83%92%e3%83%bc%e3%83%97%e3%82%bd%e3%83%bc%e3%83%88/)
*　　　マージソート...[マージソートとは](https://medium-company.com/%e3%83%9e%e3%83%bc%e3%82%b8%e3%82%bd%e3%83%bc%e3%83%88/)
*　　過去問
*　　問1...Ok
*　　問2...Ok
*　　問3...nnnn...OK

にわ：
- 読み込み
* データを整列させるアルゴリズム
* 基本交換法（バブルソート）
* 隣接するデータの大小を比較して入れ替え、を繰り返して全体を整列させる。
* 基本選択法（選択ソート）
* 対象データ内から最小値のデータを取り出し、先頭のデータとして確定。
* したら残りのデータ内で同じようにやってくことで全体を整列させる。
* 基本挿入法（挿入ソート）
* 対象データ列を「整列済み」「未整列」に分ける。
* で、未整列の中からデータを一つずつ整列済みの中に適切に入れていくことで全体を整列させる。
* UNOやる時これやってるわ。
* 上記より高速な整列アルゴリズム
* シェルソート
* 一定間隔おきに要素を取り出して部分列（順序があるグループ）とする。
* で、部分列内で必要に応じて順番を入れ替え、入れ替えた順番のままそれぞれ元の位置に戻す。
* 次は間隔を詰めて要素取り出し、再度整列。これを間隔が1になるまで繰り返す。
* クイックソート
* 中間的な基準値を決めて、それより小さい値と大きい値のグループに分類。
* それぞれのグループ内でまた基準値を決め、グループ振り分け。これを繰り返して整列。
* ヒープソート
* 未整列の部分を一旦「順序木」（親>=子とかになってる2分木）という木構造に構成
* そこから最大値or最小値を取り出して整列済みに移す。これを繰り返し、未整列を縮めていく。
* [ヒープ 【heap】](https://e-words.jp/w/%E3%83%92%E3%83%BC%E3%83%97.html#:~:text=%E3%83%92%E3%83%BC%E3%83%97%E3%81%A8%E3%81%AF%E3%80%81%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0,%E3%81%A8%E7%95%A5%E3%81%99%E5%A0%B4%E5%90%88%E3%81%8C%E3%81%82%E3%82%8B%E3%80%82)
- 過去問
* 問１：OK
* 問２：OK
* 問３：問題文の理解に時間かかったけどOK

ちさと：
* データを整列させる
* 基本交換法：隣り合わせたデータを比較して必要に応じて入れ替え、全体を整列させる
* 基本選択法：データの中から最小値or最大値を取り出して、先頭データと交換。これを繰り返して全体を整列させる
* 基本挿入法：データを「整列済」「未整列」に分ける。未整列にあるデータを整列済の適切な位置に挿入。全体を整列させる
* より高速なアルゴリズム
* シェルソート：一定間隔おきにグループ分けして間隔が１になるまで繰り返す
* クイックソート：中間の基準値を決めて、それより小さい、大きいで分ける
* ヒープソート：
* 過去問
* 問１：おk
* 問２：おk
* 問３：nとかjとかいやんなる！

まい：

* データを整列させるアルゴリズム
* 探索の次は整列。お約束としてあげられる基礎的で単純なアルゴリズムの一つ (私には単純に思えない)
* 昇順 ascending order
* 降順 descending order
* ソートの種類
* Bubble sort
* Selection sort
* Insertion sort
* Shell sort
* Quich sort
* Heap sort