🗂

アルゴリズムとデータ構造【探索・ソート】

1 min read

データ構造

ヒープ

木構造の特殊なケース。
具体的には常に親要素が子要素よりも等しいか大きい(小さい)もの。

探索

基本的

線形探索

実用的

二分探索

ハッシュ探索

データを挿入する際にそのデータ自身を使って格納位置を決定する。
格納される配列をハッシュテーブル、各要素をバケット、格納位置を決めるための計算をハッシュ関数、ハッシュ関数が返す値をハッシュ値という。
計算量はO(1)。

ソート

内部ソート、外部ソート

ソートされるデータの格納領域内のみで処理を行うソートを内部ソートという。反対に格納領域外に一時的なメモリが必要となるソートを外部ソートという。
内部ソートではその性質から計算量はO(n)かO(logn)となる。(クイックソートを含める場合)

基本的

バブルソート(線形探索)

隣あう二つの値を比較して条件に応じて交換を行う。
計算量はO(n^2)。
安定したソート。

選択ソート

最大値(最小値)を見つけ出してそれを配列最後の要素と入れ替えることでソートする。
計算量はO(n^2)。
安定でないソート。

挿入ソート

計算量は最良でO(n)、平均、最悪でO(n^2)。

実用的

クイックソート

  1. 適当な数(ピボッド)を選択(データの中央値が望ましい)。
  2. ピボッドより小さい数を前に、ピボッドより大きい数を後ろに移動させる。
  3. 分けたグループごとに1~から繰り返す。
    分割統治法を用いたアルゴリズム。
    安定ではない。
    計算量はO(nlogn)。(ただし最悪時はO(n^2))

ヒープソート

ヒープのルートには常に最大値があるという特性を生かしたソート。

  1. 二分ヒープ木を用意する。
  2. ルート(0番目)と配列最後を交換する。
  3. 配列最後を取り出して別の配列に格納。
  4. 残った木構造を二分ヒープ木にする
  5. もう一度2から行う。
    安定ではない。
    計算量はO(nlogn)。

シェルソート

  1. 等間隔にデータをグループ分けする。(例)3なら3で割った余りがそれぞれ0, 1, 2であるグループ)
  2. 分けたグループ内でソートを行う。
  3. 1よりも狭い間隔でグループ分けを行い、ソートする。
  4. 最後に間隔1で挿入ソートを行う。
    計算量の平均はO(n^1.2)、最良でO(n)、最悪でもO(nlog^2n)。

マージソート

  1. 整列されていない配列を2つに分ける。
  2. 1を要素が1つずつになるまで行う。
  3. 分けた要素を順番にマージする。マージをする際はソートした上でマージするようにする。
  4. 全ての要素がマージされるまで3を繰り返す。

Discussion

ログインするとコメントできます