本記事ではアルゴリズムについて学んだ内容を備忘録としてまとめています。
アルゴリズムの基礎知識について簡単に説明していますので、興味がある方は是非読んでみてください。
アルゴリズムとは？
アルゴリズムとは、問題解決のための処理方法です。
例えば料理などは決められた順序の通り作業し、その中で反復作業などがあったりします。
このように日常生活の様々な場面でアルゴリズムは活用されています。
ただし、一般的にはコンピュータを用いた問題解決手順を指す言葉として使われることが多いです。
アルゴリズムの種類
アルゴリズムの種類は基本的に2つに分類されます。
それが以下の通りです。
・ソートアルゴリズム
・探索アルゴリズム
まずはソートアルゴリズムについて説明していきます。
ソートアルゴリズム
ソートとは英語の「sort（整理、並べ替え）」のことで、アルゴリズムの中で最も基本的なものがソートアルゴリズムと言われます。
英語の意味の通り、データの整理や並べ替えを行うためのアルゴリズムとなっています。
ソートアルゴリズムの種類は以下の6つになります。
・バブルソート
・クイックソート
・マージソート
・選択ソート
・挿入ソート
・ヒープソート
以下ではソートアルゴリズムの種類を1つずつ説明していきます。
バブルソート
バブルソートとは、隣接する値を比較して必要であれば入れ替えを繰り返し値を整列する方法です。
実際にバブルソートを使用したときの流れを見てみた方が分かりやすいと思うので、「5→9→7→2」という配列をバブルソートで並び替えてみましょう。
①5→9→7→2 => 5と9を比較 => そのまま
②5→9→7→2 => 9と7を比較 => 入れ替え
③5→7→9→2 => 9と2を比較 => 入れ替え
④5→7→2→9 => 7と2を比較 => 入れ替え
⑤5→2→7→9 => 5と2を比較 => 入れ替え
最終結果：2→5→7→9
このように隣同士の値を比較して並べ替える方法がバブルソートです。
クイックソート
クイックソートとは、基準値を決め、基準値より大きいグループと小さいグループに値を分け、並び替えの処理を繰り返すことで整列させる方法を指します。
「5→9→7→2」という配列をクイックソートで並び替えてみましょう。
①5、9、7、2（7を基準値に大小のグループ分け） => 5、2、7、9
②5、2、7、9（5を基準値に大小のグループ分け） => 2、5、7、9
最終結果：2→5→7→9
このように基準値を設けてその基準値をもとに大小のグループに分ける処理を行い続け整列するのがクイックソートです。
マージソート
マージソートとは、データを2分割する操作を値が1つになるまで繰り返し、その後1つになった値を整列しながら配列の状態に戻していく方法を指します。
「5→9→7→2」という配列をマージソートで並び替えてみましょう。
①「5、9、7、2」（左記の配列を2分割する） => 「5、9」「7、2」
②「5、9」「7、2」（左記の2つの配列を2分割する） => 「5」「9」「7」「2」
③「5」「9」「7」「2」（左記の値を並び替えしながら配列に戻す） => 「5、9」「2、7」
④「5、9」「2、7」（左記の値を並び替えしながら配列に戻す） => 「2、5、7、9」
最終結果：2→5→7→9
このようにデータの分割を繰り返し、配列の状態に戻す段階で整列していくのがマージソートです。
選択ソート
選択ソートとは、データの中から最小値を探して先頭の値との交換していく操作を繰り返す整列方法を指します。
「5→9→7→2」という配列を選択ソートで並び替えてみましょう。
①「5、9、7、2」（最小値の「2」と先頭の「5」を交換） => 「2、9、7、5」
②「2、9、7、5」（「2」の次に小さい「5」と2番目の「9」を交換） => 「2、5、7、9」
③「2、5、7、9」（「5」の次に小さい「7」は「9」より小さいためそのまま） => 「2、5、7、9」
最終結果：2→5→7→9
このように最小値と先頭の数値を交換する作業を繰り返すのが選択ソートです。
挿入ソート
挿入ソートとは、配列の先頭から1つずつ値を取り出し、適切な位置へ挿入していく並び替え方法を指します。
「5→9→7→2」という配列を挿入ソートで並び替えてみましょう。
①「5、9、7、2」（5を取り出し配列の適切な位置に格納） => 「5」
②「5、9、7、2」（9を取り出し配列の適切な位置に格納） => 「5、9」
③「5、9、7、2」（7を取り出し配列の適切な位置に格納） => 「5、7、9」
③「5、9、7、2」（2を取り出し配列の適切な位置に格納） => 「2、5、7、9」
最終結果：2→5→7→9
このように配列から値を1つずつ取り出し、適切な位置に格納していくのが選択ソートです。
ヒープソート
ヒープソートとは、ヒープ構造という2分木を構築してからデータを並べ替える方法を指します。
「5→9→7→2→8→6」という配列をヒープソートで並び替えてみましょう。
①「5、9、7、2、8、6」（左記の配列を2分木で整理）
5
／ ＼
9 7
／ ＼ ／
2 8 6
↓
9
／ ＼
8 7
／ ＼ ／
2 5 6
②大きい値（9）から順に取り出し、配列の後ろから順に格納 => 「2、5、6、7、8、9」
最終結果：2→5→6→7→8→9
このように一度2分木を構築し（並び替えも行う）、その後に配列に値を格納する中で並び替え行うのがヒープソートです。
探索アルゴリズム
探索アルゴリズムとは複数あるデータ群の中から目的のデータを探し出すアルゴリズムを指します。
探索アルゴリズムの種類は以下の3つになります。
・線形探索アルゴリズム
・二分探索アルゴリズム
・ハッシュ探索法
以下では探索アルゴリズムの種類を1つずつ説明していきます。
線形探索アルゴリズム
先頭のデータから順に条件に合うデータを探していくのが線形探索アルゴリズムです。
探索アルゴリズムの中で最もシンプルで基本的なものとなっています。
ここで「5、9、7、2」の中から7を探す場合の線形探索アルゴリズムの使い方を見ていきましょう。
①「5、9、7、2」の中から5と探す値（7）を比較 => 不一致
②「5、9、7、2」の中から9と探す値（7）を比較 => 不一致
③「5、9、7、2」の中から7と探す値（7）を比較 => 一致（完了）
このように単純で、探すデータが最初の方で見つかれば容易に見つかります。
しかし、探すデータが最後にある場合は、すべての要素を探索する必要があるため手間がかかります。
二分探索アルゴリズム
整列された値を2グループに分け、探している値がどのグループにあるかを判断を繰り返し行い、値を見つけるのが二分探索アルゴリズムです。
ここで「1、2、5、6、7、9、10」の中7を探す場合の二分探索アルゴリズムの使い方を見ていきましょう。
①「1、2、5、6、7、9、10」の中から真ん中の値（6）と探す値（7）を比較 => 6は7より低いので「7、9、19」に絞り込む
※中間の数字がない場合は1つ左か右の値と比較する
②「7、9、19」の中から真ん中の値（9）と7を比較 => 9は7より高いので「7」に絞り込む
③最後に7と探す値（7）を比較 => 一致（完了）
このように先ほど説明した線形探索アルゴリズムよりも効率的な方法で値の探索が行えますが、データが整列されていることが前提条件となっています。
そのため先ほど説明したソートアルゴリズムを使ってデータを整列する必要があります。
ハッシュ探索法
何らかの計算式を使いデータの格納位置（格納アドレス）を特定するのがハッシュ探索法です。
この計算式がハッシュ関数というものがつかわれるためハッシュ探索法という名前がついています。
【データの格納】
①ハッシュ関数で格納する値（8）を計算する
②計算した結果が3になったため3番に値（8）を格納
【データの探索】
①ハッシュ関数で探索する値（8）を計算する
②計算した結果が3になったため3番を参照
まとめ
今回はアルゴリズムの基礎知識をご紹介しました。
最後に今回お伝えした内容をもう一度振り返っていきたいと思います。
・アルゴリズムとは → 問題解決のための処理方法
・ソートアルゴリズムとは → データの整理や並べ替えを行うためのアルゴリズム
・バブルソート
隣接する値を比較して必要であれば入れ替えを繰り返し値を整列する方法。
・クイックソート
基準値を決め、基準値より大きいグループと小さいグループに値を分け、並び替えの処理を繰り返すことで整列させる方法。
・マージソート
データを2分割する操作を値が1つになるまで繰り返し、その後1つになった値を整列しながら配列の状態に戻していく方法。
・選択ソート
データの中から最小値を探して先頭の値との交換していく操作を繰り返す整列方法。
・挿入ソート
配列の先頭から1つずつ値を取り出し、適切な位置へ挿入していく並び替え方法。
・ヒープソート
ヒープ構造という2分木を構築してからデータを並べ替える方法。
・探索アルゴリズムとは → 複数あるデータ群の中から目的のデータを探し出すアルゴリズム
・線形探索アルゴリズム
先頭のデータから順に条件に合うデータを探していく探索方法。
・二分探索アルゴリズム
整列された値を2グループに分け、探している値がどのグループにあるかを判断を繰り返し行い、値を見つける探索方法。
・ハッシュ探索法
何らかの計算式を使いデータの格納位置（格納アドレス）を特定する探索方法。
今後他にも気になる言葉や技術について当ブログでまとめていきたいと思います。
お手すきの際に確認してみてください。
