整列(ソート)
整列とは?
- データを大きい順、もしくは小さい順に並べる処理のこと
- 大きい順が降順、小さい順が昇順
選択法
- 先頭から順に一番大きい(小さい)数字を探していく
- 入れたい順番から後の数字を毎回全て見ていく
- 比較回数はn(n-1)/2
交換法(バブルソート)
- 隣り合わせのデータの大小を比較していく
- 比較回数はn(n-1)/2
挿入法
- 整列済の部分に、整列していないデータを挿入する方法
- 比較回数はn(n-1)/2
シェルソート
- 挿入法を改良したもの
- 小さい数に分割して、挿入法を繰り返す
- 列を一定の間隔で分解し、小さな列をつくり、それぞれ列ごとに挿入法を行う
ヒープ法
- ヒープ木を使った整列法
クイックソート
- 基準値を決めて小さく分解して並べ替える
- 高速なソート
マージソート
- 列を分割し、小さな列をつなぎあわせながらソートを行う
- 作業領域が必要