ソートアルゴリズムメモ
ソートのアルゴリズムをちゃんと理解したいなあと思いつつネットで調べてみたんだけど、歴史からちゃんと書いているものはないなあ。
そういう書籍ってないのかなー。
バブルソート
隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。
2つの要素について順番に比較していって大小を決めていくソート。いちばん単純なやつ。
クイックソート
1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO n\log nである。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はOn^{2}である。また数々の変種がある。 安定ソートではない。
ある基準を設定して、基準に対して値の大小で左右に数字を振り分ける。
振り分けたうち、基準より小さいものと多きもので分割する。
分割したものに対して、またある基準を設定して振り分けていく。
ヒープソート
リストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである（ヒープ領域とは無関係であることに注意する）。
アルゴリズムは、以下のように2つの段階から構成される。
未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。
計算量は O(n\log n) となる。安定ソートではない。
二分木を使って作られるヒープを利用したソート。
ヒープといえばヒープ領域を思い浮かべるが、それは全くの別物なので気を付ける。
配列の0から順番に整列して、根と葉を比較して大きいほうを根にもってくる。
シェルソート
シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる。
ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。
離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。
ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した。
ある配列に対し、大きな間隔でソートする。
それが終わったら1回目よりも小さい感覚でソートしていく。
マージソート
ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。
大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
配列を2分割し、さらに2分割した中から細かく分割して比較。
細かく分割したもの同士で比較していって、最終的に最初に分割した2分割したものを比較していくソート。
