Rainbow Engine

IT技術を分かりやすく簡潔にまとめることによる学習の効率化、また日常の気付きを記録に残すことを目指します。

Java

Javaの選択ソートとは?アルゴリズムの流れ+サンプルプログラムをご紹介

投稿日:2020年10月13日 更新日:

<目次>

(1) バイナリ―サーチとは?Javaのサンプルプログラムを用いて解説
 (1-1) バイナリ―サーチのアルゴリズム
 (1-2) バイナリ―サーチの性能(処理回数)
 (1-3) バイナリ―サーチのサンプルプログラム

(1) バイナリ―サーチとは?Javaのサンプルプログラムを用いて解説

(1-1) バイナリ―サーチのアルゴリズム

バイナリーサーチ(=二分探索=binary search)は「各レコードがキー情報でソートされている」際に使える探索アルゴリズムです(前提条件)。
全部レコードの中央に相当するキー(mid)と、求めるキーとの大小関係を比較し、探索範囲(lo~hi)を半分に絞ります(二分する)。この処理を繰り返していく事で、徐々に解に近づいていきます。

(例)
上記処理の処理の流れを、次の配列で実際に確認します(テニス選手の名前です)。この配列はアルファベット順にソート済みです。

String[] name = {"Cilic","delPotro","Djokovic","Federer","Murray","Nadal","Nishikori","Thiem","Wawrinka","Zverev"};

この配列の中から錦織選手(Nishikori)を探す場合、探索範囲の下限(★lo)、上限(★hi)、中央(★mid)の動きはそれぞれ次のようになります。

(表)

配列インデックス 0 1 2 3 4 5 6 7 8 9
配列値 Cilic delPotro Djokovic Federer Murray Nadal Nishikori Thiem Wawrinka Zverev
初期状態 ★lo o o o ★mid o o o o ★hi
繰り返し1回目 x x x x x ★lo o ★mid o ★hi
繰り返し2回目 x x x x x ★lo
★mid
★hi x x x
繰り返し3回目 x x x x x x ★hi
★lo
★mid
x x x

(表補足)
・「x」⇒midの更新処理により探索範囲外となった領域
・「o, ★lo, ★mid, ★hi」⇒現在対象となっている探索領域

目次にもどる

(1-2) バイナリ―サーチの性能(処理回数)

バイナリーサーチは繰り返しの度に探索範囲が半分になります。上表でも、繰り返す毎に探索範囲のデータは10⇒5⇒2⇒1と半減していっています。

例えば256個のデータの場合は⓪256⇒①128⇒②64⇒③32⇒⑤16⇒⑥8⇒⑦4⇒⑧2⇒⑨1と8回の比較繰り返しが行われます。

これは次のようにlogの式で表現する事ができます。
$$ \log_2 256= 8 $$

つまり、N個のデータがある場合の比較回数は次のようになります。
$$ \log_2 N $$

ただし、前提として配列がソートされている必要があり、ソート自体にも処理時間がある程度掛かる事もあるため、このアルゴリズムを使う際は「ソート+探索」の総合的な観点での評価が必要となります(例:探索を1回しかしないならソートの時間が無駄になってしまう)。

目次にもどる

(1-3) バイナリ―サーチのサンプルプログラム

(注意)
前提条件として探索対象の配列がキー情報でソートされていることが必要となります。

(サンプルプログラム)

public class IT0145_BinarySearch {
  public static void main(String[] args) {
    //探索対象の配列。探索するためにはここがソートされている必要あり。
    String[] name = {"Cilic","delPotro","Djokovic","Federer","Murray","Nadal","Nishikori","Thiem","Wawrinka","Zverev"};
    System.out.println("Serach Result : " + name[binarySearch(name,"Nishikori")] +" exists.");
  }
  static int binarySearch(String[] a, String key) {
    //lo = 比較範囲の下限のインデックス(初期値は0)
    int lo = 0;
    //hi = 比較範囲の上限のインデックス(初期値はa.length-1)
    int hi = a.length - 1;
    while(lo <= hi) {
      //midはloとhiの平均で求めます
      int mid = (lo + hi) / 2;
      //求めたい値(key)と最新の中央値(mid)の大小関係をcompareToで比較します
      int cmp = key.compareTo(a[mid]);
      System.out.println("Lo="+lo+"("+a[lo]+")"+" Hi="+hi+"("+a[hi]+")"+" Mid="+mid+"("+a[mid]+")"+" cmp="+cmp);
      //求めたい値(key) < 最新の中央値(mid)ならば
      if (cmp < 0) {
        //中央値(mid)より大きい部分には求めたい解は存在しないため
        //hiの値を(mid - 1)で更新する(=探索範囲を半分に絞る)
        hi = mid - 1;
      }
      //求めたい値(key) > 最新の中央値(mid)ならば
      else if (cmp > 0) {
        //中央値(mid)より小さい部分には求めたい解は存在しないため
        //loの値を(mid + 1)で更新する(=探索範囲を半分に絞る)
        lo = mid + 1;
      }
      //求めたい値(key) = 最新の中央値(mid)ならば
      else {
        //中央値=解のため、midを解として返す
        return mid;
      }
    }
    return lo;
  }
}

(実行結果)
上記プログラムをeclipse上で実行した結果を次に示します。

(図131)

目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

JSP/Servletで画面毎のアクセスカウンターを作成してみた(パート2:ソース解説編)

(1) 仕様について (2) ソースコード  (2-1) AccessCounter2.java   (2-1-1) サンプルPG   (2-1-2) サンプルPG解説  (2-2) DbConnec …

Tomcatの起動時のエラー「アドレスは既に使用中です」や「必要な幾つかのポートがすでに使用中です」の対処方法

<目次> (1) Tomcatの起動時のエラー「アドレスは既に使用中です」や「必要な幾つかのポートがすでに使用中です」の対処方法  (1-1) 発生状況  (1-2) 原因  (1-3) 対処方法 ( …

JavaのArrrayListとLinkedListの違いについて

<目次> (1) JavaのArrrayListとLinkedListの違いについて  (1-1) 比較表(ArrayList vs LinkedList)  (1-2) まとめ  (1-3) 参考 …

JavaのhashCode()で31を掛け算する理由について

<目次> (1) JavaのhashCode()で31を掛け算する理由について  (1-1) ハッシュの計算のソースコード  (1-2) ソースコードに登場する代表的な変数  (1-3) ソースコード …

Javaのswitch-case文の構文や使い方を紹介+UFOキャッチャーの座標移動プログラムも紹介

<目次> (1) Javaのswitch-case文の構文や使い方を紹介  (1-1) switch-caseの構文  (1-2) else-if文との比較 (2) サンプルプログラムの紹介  (2- …

  • English (United States)
  • 日本語
Top