プログラミング学習をしていると「アルゴリズム」という言葉に遭遇する機会は頻繁に訪れますが、難しいと感じてしまい避けてしまう方が多いのも事実です。
本記事では、プログラミング初心者向けにアルゴリズムの概要と定番アルゴリズムの処理内容について、基本となる知識をご紹介していきたいと思います。
アルゴリズムって何？
そもそも「アルゴリズム」という言葉についてですが、「問題解決の手順や方法」のことを指します。
よく目にする表現としては「Googleの検索アルゴリズムが変更された」などは聞いたことがある方も多いのではないでしょうか？
アルゴリズムは重要
アルゴリズムが手順や方法を意味すると述べましたが、処理手順や方法が異なるだけで、プログラムの実行時間が大幅に変わることも少なくありません。
特にJavaを始めとしたコンピュータープログラミングでは大容量のデータを扱うことも多く、アルゴリズムによる最適化が必要となるケースも存在します。
アルゴリズムを学ぶべき理由
アルゴリズムを学ぶことで、上述したように処理速度を意識したプログラミングが出来るようになるメリットがあります。
また、アルゴリズムにより問題解決力の向上も期待出来ることから、システム開発の仕組みを考えたりエラーを解決する際の対応力が向上するといった点もメリットです。
アルゴリズムの種類
目的に応じて様々な種類のアルゴリズムが存在し、手順や方法毎にアルゴリズムの名前が付けられています。
例えば「サーチアルゴリズム」や「ソートアルゴリズム」といったものが挙げられます。
サーチアルゴリズム
サーチアルゴリズムは探索アルゴリズムとも呼ばれるもので、まとまったデータの中から目的のデータを探し出すために使用されるアルゴリズムです。
代表的なものには「線形探索アルゴリズム(リニアサーチアルゴリズム)」や「二分探索アルゴリズム(バイナリサーチアルゴリズム)」などがあります。
線形探索アルゴリズム
線形探索アルゴリズムは、先頭(端)のデータから順番に目的のデータが見つかるまで検索する方法です。
目的のデータが先頭に近ければすぐに結果を得られる反面、最後尾に近いほど結果を得るまでに時間が掛かります。
二分探索アルゴリズム
二分探索アルゴリズムは、対象データを2分割して大小により絞り込んでいき、最終的に目的のデータにたどり着くまで繰り返す検索方法です。
データに規則性があることが条件とはなりますが、線形探索アルゴリズムよりも効率的な検索が可能です。
後述するソートアルゴリズムでデータを規則的に並び替えた後、二分探索アルゴリズムで検索する方法などが利用されます。
ソートアルゴリズム
ソートアルゴリズムは整列アルゴリズムとも呼ばれるもので、データのかたまりを一定の規則に従って並び替えるために使用されるアルゴリズムです。
代表的なものには「バブルソート」や「クイックソート」などがあります。
バブルソート
バブルソートは隣接するデータを比較し、入れ替えを続けることでデータを昇順または降順に並び替えるアルゴリズムです。
並び替えによりデータが左右に移動していく様子からバブルソートと呼ばれています。
クイックソート
クイックソートは、データのかたまりから基準となる値を決めて、基準値より大きいか小さいかにより並び替え処理を行うアルゴリズムです。
1つ目の基準値で並び替えが完了した後、小さいグループ大きいグループでそれぞれ基準値を決めて繰り返し並び替えを行います。
名前の通り、高速なアルゴリズムとされており、一般的にはバブルソートよりも高速で整列処理が行えます。
Javaのアルゴリズムサンプル
ここまでで定番アルゴリズムを紹介してきましたので、簡単なJavaのサンプルプログラムで具体的な処理内容を確認していきましょう。
今回はサーチアルゴリズムから「線形探索アルゴリズム」と、ソートアルゴリズムから「バブルソートアルゴリズム」をJavaでのサンプルコードで掲載します。
線形探索アルゴリズムサンプル
配列形式のデータから指定した値を線形探索アルゴリズムで検索してみます。
public class Main {
public static void main(String[] args) {
int[] array = {1, 11, 5, 9, 13 , 7, 3};
int findResult = linearSearch(array, 9);
if(findResult == -1) {
System.out.println("目的のデータは見つかりませんでした。");
} else {
System.out.println(findResult +1 + "番目で目的のデータが見つかりました。");
}
}
static int linearSearch(int[] array, int target) {
for(int i=0; i<array.length; i++) {
if(array[i] == target) {
return i;
}
}
return -1;
}
}
実行結果は下記です。
4番目で目的のデータが見つかりました。
「lineSearch」と名付けたメソッドに配列と対象データを渡して、先頭から順番に対象データが見つかるまで検索処理を実施しています。
バブルソートアルゴリズムサンプル
配列で定義したランダムな値をバブルソートで昇順に並び替えるサンプルです。
public class Main {
public static void main(String[] args) {
int[] array = {1, 11, 5, 9, 13 , 7, 3};
bubbleSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
static void bubbleSort(int[] array) {
for (int i = 0; i i; ii--) {
if (array[ii - 1] > array[ii]) {
int tmp = array[ii - 1];
array[ii - 1] = array[ii];
array[ii] = tmp;
}
}
}
}
}
実行結果が下記です。
1 3 5 7 9 11 13
二重ループを使って隣同士の値を入れ替えながら配列データを並び替えています。
さいごに: アルゴリズムを学習してJavaコードの最適化を目指そう
本記事では、アルゴリズムについての概要と定番アルゴリズムの内容について、Javaでのサンプルコードを掲載しながらご紹介してきました。
アルゴリズムはプログラム初心者の方はもちろん、プログラマーとして働いている方にも苦手意識を持っている方は多くいますが、コードを最適化するためには身につけておくべき知識です。
様々なアルゴリズムがありますので、まずは今回ご紹介した基本とも言える定番アルゴリズムから徐々に難易度の高いアルゴリズムに挑戦してみてください。
