探索、整列アルゴリズム

探索

リストや配列の先頭から順に要素を比較し、目標の要素を見つけるまで判定していく探索アルゴリズム整列されていないものに対しても整列できるが、あまり効率的ではない。

計算量 : O(n)

リストが昇順または降順で整列されていることが前提とされる探索アルゴリズム目的の値が探索するリストの中央の値より大きいか小さいかを判断して次の探索範囲を絞りこみ、それを繰り返す。

計算量 : O(log n)

隣接する要素を比較し、順番が逆であれば交換するという操作を繰り返す。

計算量 : O(n²)

データ列を未整列と整列済の2つに分けて、未整列の最小の要素を選び、整列済みの末尾に付け加える操作を繰り返す。

計算量 : O(n²)

データ列を未整列と整列済の2つに分けて、未整列の最小の要素を1つ選び、整列済みの適切な位置に付け加える操作を繰り返す。

計算量 : O(n²)

一定間隔が離れた要素おきのグループをそれぞれで整列して、間隔を狭めていきながら挿入ソートを繰り返す。

ピボットと呼ばれる要素を1つ選び、それを基準としてそれより小さい要素と大きい要素に分割して、再帰的に繰り返す。

データ列を2分割して、それぞれをマージソートした後それらをマージすることを繰り返す。

初めにヒープ木を構成して、その後にヒープの先頭から最大(または最小)の要素を取り出す操作を繰り返す。