整列２（sort）
ソートアルゴリズムの速度の比較
種類
平均
最悪
備考
バブル
O(N
2
)
O(N
2
)
選択
O(N
2
)
O(N
2
)
挿入
O(N
2
)
O(N
2
)
シェル
O(N
3/2
)
O(N
3/2
)
クイック
O(NlogN)
O(N
2
)
マージ
O(NlogN)
O(NlogN)
ヒープ
O(NlogN)
O(NlogN)
マージソート（merge sort）
２つのソート済み配列をマージする
元の配列と同サイズの作業スペースを必要とする
New
新しい配列を作る
Size
サイズを変更する
Draw
図形を描きなおす
Run
自動実行を開始する
Step
シングルステップ実行する
シェルソート（shell sort）
ソートの歩幅を大きなものから狭めながら挿入ソートを進める
New
新しい配列を作る
Size
サイズを変更する
Draw
図形を描きなおす
Run
自動実行を開始する
Step
シングルステップ実行する
クイックソート（quick sort）
配列を２分割し、部分配列に対して再帰的にソートを行なう
分割がうまくいかないと O(N
2
) になってしまう
New
新しい配列を作る
Size
サイズを変更する
Draw
図形を描きなおす
Run
自動実行を開始する
Step
シングルステップ実行する
分割値（pivot value）として、右端のデータを選んでいるので、 逆順にソートされていた場合には最悪の状態になる
クイックソート（quick sort）改良版
New
新しい配列を作る
Size
サイズを変更する
Draw
図形を描きなおす
Run
自動実行を開始する
Step
シングルステップ実行する
分割値（pivot value）として、
３のメジアン
（median-of-three）を使っている （最初、中央、最後の３つの値のメジアンを分割値として選ぶ）
ヒープソート（heap sort）
ヒープ
を用いたソーティング
