こんにちは。いつもブログをご覧いただきありがとうございます。
今回はアルゴリズムについて解説を行います。プログラミングで重要な探索やソート処理の仕組みについて学んでいきましょう！
もっとも基本的なアルゴリズムについて一緒に学んでいきましょう。
今回、紹介するアルゴリズムの種類か以下の３つ。
- 線形探索
- ２分探索
- スタック
１つずつ解説しますね。
線形探索
複数の数値・文字列の中から、対象の数値・文字列が見つかるまで順次探索するアルゴリズムになります。
例えば、５つのランダムな数値（41、27、35、18、50）が存在しているとします。そしてその中から「35」という数値を探索する場合とします。
まず、最初の数値41と探索したい35を比較します。同じ数値ではないため、次の数値と比較を行います。次は数値27と35を比較します。これも違います。
というアルゴリズムで対象の数値、文字列が見つかるまで探索を行うアルゴリズムになります。
サンプルコード
import java.util.Random;
public class App {
public static void main ( String[] args ) {
int[] element = new int[5];
Random random = new Random();
for ( int i = 0; i < element.length; i++ ) {
element[i] = random.nextInt(99);
System.out.println(element[i]);
}
int key = random.nextInt(99);
System.out.println( "探索する数値 " + key );
boolean result = search( 5, element, key );
if (result) {
System.out.println( key + " 対象の値が見つかりました" );
} else {
System.out.println( key + " 対象の値が見つかりませんでした" );
}
}
static boolean search ( int renge, int[] element, int key ) {
int count = 1;
while(true) {
if ( count == renge ) {
return false;
}
if ( element[count] == key ) {
return true;
}
count++;
}
}
}サンプルコードの解説を行います。
Random random = new Random();
element[i] = random.nextInt(99);ランダムな数値を生成するため、Randomクラスを使用しています。そしてnextIntメソッドを使用して、数値の範囲を0~99としています。
２分探索
要素がソート（昇順 又は 降順）されている条件で、線形探索より効率良く・高速に探索が行えます。下記の図をもとに探索方法について見ていきましょう！
まず１~50までを範囲として要素数が11個あるとします。
そしてその中から「20」という数字が何番目に存在するかを確認する２分探索を行います。
数値はランダムではなく、昇順（小さい順）に並んでいることが条件になります。
最初は要素中央である25と比較します。探索する数値は20でしたよね。
「25 > 20」となるため、要素を一気に半分に絞り込みます。
次に、探索する要素中央の10と比較を行います。探索する数値は20なので「10 < 20」となります。
次に、15と20を比較します。最後に20を見つけることができました。
インデックス（0から数えて）は４になります。
このように探索対象を減らしながら目的を達成する感じになります。
上記を元にサンプルコードを記載します。
サンプルコード
public class App {
public static void main ( String[] args ) {
// 探索要素 (1 ~ 50までの11個の要素を生成)
int[] element = new int[11];
element[0] = 1;
for (int i=1; i < 11; i++) {
element[i] = i*5;
}
// 探索対象の値
int key = 20;
// 2分探索の実行
int index = search(element, key);
// 2分探索の実行結果
if (index == -1) {
System.out.println("存在しません");
} else {
System.out.println("存在しました " + index);
}
}
/**
* 2分探索
* @param element 探索要素
* @param key 探索する値
* @return 探索対象の位置
*/
public static int search ( int[] element, int key ) {
int left = 0;
int right = element.length - 1;
do {
int center = (left + right) / 2;
if ( element[center] == key ) {
return center;
} else if (element[center] < key ) {
left = center + 1;
} else {
right = center - 1;
}
} while ( left <= right );
return -1;
}
}■実行結果
存在しました 4
スタック（Stack）
スタックは一時的にデータを格納するためのデータ構造になります。
データを格納したり、取り出したりする手順について見ていきましょう！
まず最初に【A】を格納します。次に【B】を格納します。更に【C】を格納します。この中からデータを取り出す場合、箱の一番上にある【C】から取り出すことになります。
つまり、後から格納した値から取り出す方式となり、後入れ先出しと呼ばれています。
後入れ先出し：LIFO（Last in First Out）です。
Java言語では「Stackクラス」という標準APIが用意されており、これを使用することでスタックを実現することができます。
サンプルコード
import java.util.Stack;
public class StackSample {
public static void main ( String[] args ) {
Stack<String> stack = new Stack<String>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.pop();
System.out.println(stack);
}
}「図１．データ格納の仕方」の通り、サンプルコードを書きました。
Stackクラスを生成し、pushメソッドでデータの格納、popメソッドでデータの取り出しを行っています。
■実行結果
[A, B]
popメソッドを１回実行したため、Cが取り出され、箱の中には「A、B」が残っている事がわかります。
実は、Stackクラスの後継者というか、、、Java 6から「Deque」というインターフェースが誕生しています。現在はこちらを使用することが主流なようです。
import java.util.ArrayDeque;
import java.util.Deque;
public class StackSample {
public static void main ( String[] args ) {
Deque<String> deque = new ArrayDeque<String>();
deque.addFirst("A");
deque.addFirst("B");
deque.addFirst("C");
deque.removeFirst();
System.out.println( deque );
}
}本記事のまとめ
今回は、アルゴリズムの種類について解説しました。
最後まで読んでいただきありがとうございます(*^-^*)
アルゴリズムの学習方法について下記の記事で詳しく解説しています。合わせてどうぞ！
おすすめ記事
「Javaプログラミングをもう一度本格的に勉強したいっ！」という方へ
逆に、「Javaプログラミング以外を本格的に勉強したいっ！」という方へ
