有名アルゴリズムを一言で
ソートアルゴリズム
初等ソート
挿入
ソート済み配列の正しい位置に挿入していく。O(n2)
バブル
後ろから前に隣り合う要素の並びを揃えていく操作を、要素数分行う。O(n2)
選択
小さい順に前に持ってくる。O(n2)
シェルソート
K個飛ばしに挿入ソートを行う。Kを適切に減らして繰り返す。最後にK=1で普通の挿入ソートを行う。O(n1.25)
高等ソート
マージ
長さNの配列を、長さ1のソート済み領域N個と見なす。隣り合う領域のマージを繰り返すことで、領域の長さを倍に領域数を半分にしていくことで、最終的に長さNのソート済み領域1個となる。O(nlogn)
クイック
基準値を選び、基準値よりも小さい領域と大きい領域に分け、基準値を真ん中に持ってくる(=パーティション)。これで基準値は位置が確定し、それぞれの領域数が1になるまでこの操作を繰り返す。O(nlogn)
計数
要素の値の出現数を記録した配列を作成し、累積和をとる。この配列はソート後の位置になっている。改めて要素を見ていき、配列の値が指す位置に格納する。この時、一個格納するごとに値は減らす。O(n+k)
グラフアルゴリズム
プリム(最小全域木)
行ったことのないノードへ行けるパスの中から最小の辺を選んでいく。O(ElogV)
クラスカル(最小全域木)
小さい順に辺を木に追加していく。追加によって閉路ができてしまう辺はスキップ。O(ElogV)
ダイクストラ(単一始点最短経路)
行ったことのないノードへのコストが更新できれば更新したのち、行ったことのない中で最小のコストで行けるノードへいく。O((E+V)logV)
ベルマンフォード(単一始点最短経路、負の辺があってもOK)
全てのエッジについてコストを更新していく操作を、|V|-1回を上限に更新がなくなるまで繰り返す。O(EV)
ワーシャルフロイド(全点対間最短経路、負の辺があってもOK)
あるノードを選び、全てのノードの組み合わせについてそのノードを通った方がコストが下がればそのノードを通るルートを採用する。これを全てのノードについて繰り返す。O(V3)