整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計についてまとめました。
[latexpage]
【整列】バブルソート、クイックソートなど
リストの整列アルゴリズムは「選択ソート」「挿入ソート」「バブルソート（交換法）」「クイックソート」などが有名です。
それぞれの特徴は以下の通り。
| 手法 | 特徴 |
|---|---|
| 選択ソート | 未整列部分の中で最小値を求め、最小値の要素を未整列部分の先頭要素と入れ替えることを繰り返すことでソートします。 |
| 挿入ソート | 未整列部分の先頭から要素を取り出し、取り出した要素を整列済み部分の順序関係を保つよう挿入することを繰り返すことでソートします。 |
| シェルソート | 挿入法を改良したもので、リスト全体のデータに対して、ある間隔でデータを取り出した部分列を整列し、さらに間隔をつめた部分列を取り出して整列する方法です。挿入法よりも後ろにずらすデータ量が少なくなり効率が改善されます。 |
| バブルソート(交換法) | 全ての要素に関して，隣接する要素と比較し順序が逆であれば入れ替える手法。これを交換が行われなくなるまで繰り返す。計算時間のオーダーは$O(N^2)$となり、データ量が2倍に増えると、並べ替えに要する時間は4倍に増大する。 |
| クイックソート | 適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割します。続いてグループの中でもさらに基準値を選び、それぞれのグループを分割します。この操作を繰り返してソートします。 |
| マージソート | 整列されていないリストを2つのリストに分割し、それぞれを整列させた後、それらを結合（マージ）して整列済みのひとつのリストにします。 |
| ヒープソート | 未整列の部分を順序木にし、そこから最小値(または最大値)を取り出して整列済の部分に移す操作を繰り返し、未整列の部分を縮めていく整列手法です。 |
【併合】
【探索】
| – | 探索 |
|---|---|
| ハッシュ法 | ハッシュ法とは、データ探索方法の1つです。データの探索キーの値からデータの格納位置をハッシュ関数を用いて直接計算します。表では、レコードのキー値とハッシュ関数を用いて格納アドレスを求めることでデータにアクセスします。 |
| 2分探索法 | 探索対象のデータが昇順 or 降順に整列されていることが条件として、探索範囲の中央に位置する値と目的の値を比較して探索範囲を1／2に狭めることを再帰的に繰り返して目的のデータを探索するアルゴリズムです。 |
| 線形探索法 | 配列の先頭から順番に探索するシンプルなアルゴリズム。 |
【再帰】
再帰関数|関数の中からその関数自身を呼び出すような処理を行う関数のことです。再帰呼び出しを行うと、関数を呼び出すたびに引数やローカル変数がメモリを確保します。
●【再帰関数とは】基本情報技術者試験の例題
【文字列処理】
【流れ図の理解】
【アルゴリズム設計】
| – | 関連記事 |
|---|---|
| 1 | ■【情報処理入門】基礎用語・原理・資格まとめ |
コメント