どうもきよです！
今回は整列のアルゴリズムについて勉強したことを
メモしていきたいと思います。
■参考文献(アフィリエイトリンクです！良かったら購入してください！)
平成30年度【春期】【秋期】応用情報技術者 合格教本 (情報処理技術者試験)
かなり詳しく書かれているのでぜひ！
■整列のアルゴリズムとは
・データをある規則に従って並べ替える方法
・整列(ソート)という
■バブルソート
・隣あう要素の値を比較し大小を入れ替える整列(ソート)
・隣接交換法ともいう
■単純選択法
・未整列のデータから最大または最小のデータを取り出し、先頭の要素と入れ替えて並び替える
■単純挿入法
・未整列リストから最大または最小のデータを取り出し、整列済みリストの先頭から順に埋めていく方法
■整列法の考え方
・逐次添加法
・下記のソート法が当てはまる
– バブルソート
– 単純選択法
– 単純挿入法
・分割統治法
・下記のソート方が当てはまる
– クイックソート
– マージソート
■クイックソート
・高速な整列のアルゴリズム
・未整列リスト内の中間値を設定し、大小の２つの区分を設ける。これを１つになるまで続けソートする
・逐次添加法のソートと比べると高速だが、安定性が低い
■ヒープソート
・ヒープ = 親は子より常に大きいか小さいかのを満たしている
・下記手順を繰り返して行われる
1.未整列データを木構造(順序木)にする
2.親を最大または最小値に設定する
3.並び替えが完了後、整列済みデータとして親のデータを確定する
下記サイトが参考になりました。
ヒープソート図解
■マージソート
・未整列リストを分割する
・分割されたリストごとに、大小比較をし並び替え、並び替えたリスト同士を大小比較をしながらマージする
ヒープについては応用情報の本を読んでいるとたくさん出てくるので
詳しく勉強していきたいと思います。
最後にまたアフィリエイトリンク貼らせてくださいorz
■参考文献(アフィリエイトリンクです！良かったら購入してください！)
平成30年度【春期】【秋期】応用情報技術者 合格教本 (情報処理技術者試験)
以上、よろしくお願いいたします。