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