整列・併合・探索のアルゴリズム
- ソート
データの順番を規則に従って整列させることです。- 選択ソート
対象データの中から最小のデータを先頭に置き、残りのデータの中から最小のデータを残りのデータの中の先頭に置き…を繰り返すソート方法です。計算量はO(N2)です。 - バブルソート
先頭から隣り合うデータの大きさを比べ、順番通りでなかったら入れ替える作業を繰り返すソート方法です。計算量はO(N2)です。 - マージソート
要素が2つになるまでデータ列を半分に分割していき、並べ替えをした後、結合、並べ替えを繰り返して整列する方法です。計算量はO(N×logN)です。 - 挿入ソート
左から数値を適切な場所に入れていくソートです。計算量はO(N2)です。 - シェルソート
一定間隔を開けてデータを取り出して挿入ソートをし、だんだんその間隔を狭めて挿入ソートを行っていく方法です。 - クイックソート
通常データのソート方法では最速と言われています。基準データ(ピボット)を定め、それと比較して大きさを左右にわけます。これをその分けたデータの中でも繰り返すことでデータを整列します。計算量はO(N×logN)です。 - ヒープソート
データを2分木にルートの値が最大値または最小値となるように配置した後、ルートの値を取り出して残りを再度2分木にすることを繰り返す方法です。
- 選択ソート
- 探索
目的データを見つける作業のことです。- 線形探索法
先頭から順番に目的データを探します。計算量はO(N)です。 - 2分探索法
整列されたデータの中央値と目的データの大小を比べ、大きい時は右側を小さい時は左側を調べます。その後調べるデータの中央値とまた比較する動作を繰り返して目的データを見つけます。計算量はO(logN)です。 - ハッシュ表探索法
ハッシュ関数という関数を用いて格納場所を決定&特定する方法です。決定するときに格納場所が被ることがあるのでその対策が必要です。計算量はO(1)です。
- 線形探索法