概要
ソートアルゴリズムについて、何度勉強しても忘れてしまうので、自分の学習用として、各ソートの概要と、理解するためのyoutubeのリンク集を纏めました。
目次
ソートの種類
その他の用語
ソートの種類
内部ソート
クイックソート
1960年にアントニー・ホーアが開発したソートアルゴリズム。
ランダムなデータをソートする際にとても速いとされている手法。
「基準値」を決め、そこから大小二つのグループに分けていく方法を繰り返す。
インプレースソートなので、メモリを節約できる。
バブルソート
ソート手法の中でも有名なソート方法。
隣同士を比較して、どちらの値が大きいか (小さいか) で、隣同士を入れ替えるかどうかを判断していく。
「バブルソート」という名称は、ケネス・アイバーソン が1962年に出版した本 「A Programming Language」に由来すると考えられている。
挿入ソート
インプレースソートの一つ。
あらかじめ整列されているデータに新しくデータを追加する際に効果的な手法。
選択ソート
インプレースソートの一つ。
数あるランダムなデータの中で最小値を探し (選択し) 、値が小さい順に並べていく手法。
シェルソート
インプレースソートの一つ。
挿入ソートや選択ソートを改良化したソート法として知られている。
1959年にドナルド・シェルが考案した。
ざっくりとデータを大小の順に並べておき、最終的に挿入ソートを使用して綺麗に並べるという手法。
ヒープソート
インプレースソートの一つ。
ヒープ (heap) とは、「積み重なる」や「堆積する」といった意味をもつ。
完全二分木を使用する。
二分木とは、全てのノードの子ノードが2つ以下のツリー構造のことを指す。「完全二分木」は「二分木」の中でも、全ての葉が同じ「深さ」を持つ二分木を指す。
ランダムなデータを完全二分木の構成にし、そこから最小値 (最大値) を取り出して整列させるということを繰り返す。
外部ソート
マージソート
既に整列してある複数個ある列を、1個の列にマージする際に有効的な手法。
外部ソートに対しても適用できる。
その他の用語
内部ソート
パソコンのメモリ上の配列のみでソートを行うことを内部ソートと呼ぶ。
外部ソート
外部記憶装置（ディスクや磁気テープ）とやり取りを行いながらソートを行うことを外部ソートと呼ぶ。