ソートの話 - LOG>>KYO2009

編集

そうです、
そうっとソートいたしましょう。

（コラ

ソートの種類ですか？
たくさんありますよ。

wikiを見ればわかりますが

さて、次の種類が主なソートです。

バブルソート
選択ソート
挿入ソート
シェルソート（挿入ソートの改良）
マージソート（分割統治）
ヒープソート
クイックソート
基数ソート(バイナリソート)

[1]バブルソートは、頭からスタートして
隣を比較しながら、ソートしていきますね。
これ、一般人のする並べかえと同じです。
小学生もやるんではないでしょうか？
先頭と次を比べて交換していくの
すごいじかんが　かかるけど
計算量の単位オーダを用いると
平均計算量は、なくて
いつでも、O（n^2）です。
ちなみに”^”ってのは、累乗です。
基本ですね
バブルソートソース

なんか、いろいろ、こってたら時間たつんで
つぎ！

[2]セレクションソートです。
選択ソートです。
バブルは、全部比較して交換してを繰り返しますが。
選択は、選択します。
n=10の場合
1~10番目を見て、最小の値を配列の1番目に入れます。
次は、それを除くn=9の中の1~9番目を見て
最小の値を配列の2番目に入れます。
これを繰り返します。
バブルと似たソースになりますが
オーダーは
最悪平均ともにO（n^2）です。
通常安定してますが
安定感を除くこともできます。

[3]インサートソート（挿入ソート）
ほぼ並んでいる列には強いので
クイックソートされた列のどこかに値を挿入し
それをソートする時に用いる方法
値を挿入し、挿入した値に対して
大きいか小さいかによって左右に振り分ける
選択ソートに比べて、比較回数が少なくなる
平均O（n+d）※ｄは、置換のときの反転数
最悪O（n^2）

[4]シェルソート
シェル
ラルクアンシエルとは、ちがうか
D.L.SHELLさんが考案したアルゴリズム
大きいか小さいかで大雑把にソートして
それを挿入ソートで仕上げる。
最悪O(nlog^2n)

[5]マージソート
配列の分割を行い、配列数がn=2以下になったときに
比較し、すべて比較し終わったら
配列をくっつけながら、比較していく。
分割統治法とも言う。
平均最悪ともにO（nlogn）である。
安定している。

[6]ヒープソート
木構造を用いて行う。
topが最小で
bottomが最大になるような木をヒープという。

[7]クイックソート

[8]基数ソート