概要
分類を意味する英単語である。そこから、データベースなどでデータを特定の順序に並べ替えることをソート、ソーティングと呼ぶ。
並べ替える基準は場合によって異なる。例えば、ある学校の生徒のリストを考えれば、名前順にソート、学籍番号順にソート、所属する学部毎にソート、学年毎にソート……等々と利用目的に応じて様々なソートが考えられる。
プログラミングに於いてソートというのは基本ではあるが、どのような手法のソートが最良か、というのは難しく、現在までに多くのアルゴリズムが考えられており、必要なソートのスピード、能力などによって使い分けられている。
安定性
同じ値のデータが複数ある場合に、元の順序を維持するソートを安定ソートと呼ぶ。例えば次のようなデータを学年順にソートすると考える。
| 学年 | 学籍番号 |
|---|---|
| 4 | 0001 |
| 3 | 0002 |
| 2 | 0001 |
| 4 | 0002 |
| 3 | 0001 |
| 1 | 0002 |
| 1 | 0001 |
この場合、学年順にソートした場合に
| 学年 | 学籍番号 |
|---|---|
| 4 | 0001 |
| 4 | 0002 |
| 3 | 0002 |
| 3 | 0001 |
| 2 | 0001 |
| 1 | 0002 |
| 1 | 0001 |
となることが保証されているものを安定ソートと呼ぶ。
平均計算量/最悪計算量
入力されるリストのデータ数nに対し、どれだけの計算量（ソートの比較）があるかの指標である。一般的には平均計算量が少なければ少ないほど優れたソートアルゴリズムであるとされる。一方で最悪計算量はそのアルゴリズムで最も不利なデータが入力された際に掛かる時間である。
代表的なソートアルゴリズム
詳細はWikipediaなどを参考にして頂きたいが有名なソートアルゴリズムを以下に挙げる。
- バブルソート
- 選択ソート
- クイックソート
- マージソート
ピクシブに於けるソート
ピクシブではキャラクターを人気順に並べ替えて、その上位キャラクターを描くというキャラソートとして用いられることが多い。
