Pythonで学ぶアルゴリズム 第22弾：並べ替え（ソート方法の比較）

#Pythonで学ぶアルゴリズム< ソート方法の比較 >

##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第22弾として今まで学んできたソートアルゴリズムの処理能力の比較および安定ソートを扱う．

##ソートアルゴリズムの比較
#####計算量での比較
表1に示すのは，各ソート方法におけるオーダー記法での処理速度である．

大前提として，「すべてにおいて最適」というような処理は存在しない．それぞれの処理に特徴がある．
例えば，表1において，下段３つのソート方法は同じ平均計算時間となっているが，ヒープソートは並列化できないことなどが理由で，あまり使われていない．マージソートは並列処理は可能だが，大量のデータをソートする際には大容量のメモリが必要となる．

利用する際には，個々の処理の違いを理解し，比べられる判断力が求められる．

#####実データでの比較
表2では，大きな実データ(10,000~30,000)を使って，各ソート方法の処理時間を比較している．ただし，表2における値は参考文献の著者の手元にあった環境での結果である．

Pythonで標準で用意されているsortは，内部でC言語のプログラムが動いているため，大幅に高速な処理が実現できている．
表2から得られる大事なことは，**「たとえオーダー記法が同じであっても，処理時間は同じにはならない」**ということである．オーダー記法を学んだ一番初めに戻ると，確かに定数倍を省略してきていたことを思い出せる．オーダー記法において違いがあれば，定数倍の影響は小さく無視できるというものであったが，同じオーダー記法であるならば，その定数倍というのも大きな影響を持ち得ることは容易に理解できる．ゆえに，例えばバブルソートが選択・挿入ソートよりもかなり遅くなるということが起きている．

##安定ソート
ソート方法を比較するときに知っておきたいキーワードらしい．．．
安定ソート: 同じ値をもつデータにおけるソート前の順序がソート後も保持されていること

例えば，名前の五十音順で並べられた学生のテスト結果を，点数で並べ替える場面を考える．
そのイメージ図を次に示す．

点数の高い順に並べ替えられている．上図において赤で囲んだ部分に着目すると，同じ点数である．しかし，出席番号を見ると，小さいものが上になっている．つまり，「ごうだ」と「ほねかわ」の並びの前後関係はソート前と同じである．
これが安定ソートの定義が意味していることである．
なお，今まで触れてきたソート方法の中では，**「挿入ソート」「バブルソート」「マージソート」**が該当する．

##感想
「オーダー記法が同じでも処理時間は異なる」
今まで，当たり前のようにオーダー記法において定数を省略してきていたため，忘れかけていた．ここで改めて思い出せてよかった．また，安定ソートは聞いたことなかったが，理解できた．次回は並べ替えアルゴリズムシリーズの最後の「ビンソート」である．

##参考文献
Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社