整列アルゴリズム

①隣接交換法(バブルソート)
バブルソートは、
隣接する要素同士を比較し、目的の順序に並んでいなければ、その要素同士を交換する。
それを配列の末尾から先頭に向かって行い、先頭まで来たら末尾に戻って同じことを繰り返す。
この操作を行うと、配列の先頭から順番に並び替えが確定していくことになるが、
これが泡が浮き上がってくるように見えるらしいことからバブルソートという名前が付けられた。

②選択法
選択ソートは、ソート対象となる配列の中から、最小あるいは最大の値をもつものを探し、それを先頭要素と交換する。
次に2番目に小さいあるいは大きいものを探し、先頭から2番目の要素と交換するという処理を繰り返すことによってソートを行うアルゴリズム。

③挿入法
挿入ソートは、配列の先頭付近をソート済みの状態にしておき、
後続の要素を1つずつ適切な位置に挿入していくことで全体をソートするアルゴリズム。

④クイックソート
クイックソートの考え方は、全体の中から基準となる要素を1つ選び(この要素を枢軸やピボットと呼ぶ)、
これより小さい要素と大きい要素とに分割する。分割された2つの要素群については、更にその中で分割を行う。
これを繰り返していくと、最終的には要素が1つ1つばらばらな状態にまで分割される。
この状態になったら、今度はそれを一気に結合する。
分割処理は、要素の大小関係によって行われているので、最終結果を結合すれば既にソート結果が出来上がっているということ。

⑤シェルソート
シェルソートは、ある一定距離だけ離れた要素同士で交換処理を行い、
この距離を少しずつ縮めていき、最後には普通に挿入ソートを実行することでソートを行う。

⑥マージソート
マージソートは、データ全体を一旦2つのデータ列に分け、それぞれを個別にソートした後、1つのデータ列にマージする。
その結果、全体がソートされた状態になる。
大量のデータをメモリ上でなく、ファイルを利用して整列する場合などに使われる。

⑦ヒープソート
ヒープ(木というデータ構造の一つ)を用いてソートを行う。
ヒープを利用すると、少ない比較回数で最大値(または最小値)が求められるので、これを利用している。
選択法の改良版。

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License