現場で「このアルゴリズムを使え」ってのは言われたことが無いですが、、、

探索

線形探索
- 直線状に並んだ要素から、目的のキーに出会うまで最初から順番に走査する
- 逐次探索ともいう
- 終了条件要素が発見できない要素が発見できた
- 番兵法検索するデータの末尾に検索キーと同じ値を格納する線形探索を行う必ず要素が見つかるので以下のメリットがある終了条件は「要素が発見できた」のみになるただし見つかった要素が番兵なのかどうかチェックする必要がある
  - 要素が発見できない
  - 要素が発見できた
  - 検索するデータの末尾に検索キーと同じ値を格納する
  - 線形探索を行う必ず要素が見つかるので以下のメリットがある終了条件は「要素が発見できた」のみになるただし見つかった要素が番兵なのかどうかチェックする必要がある
  - 必ず要素が見つかるので以下のメリットがある終了条件は「要素が発見できた」のみになるただし見つかった要素が番兵なのかどうかチェックする必要がある
  - 終了条件は「要素が発見できた」のみになる
  - ただし見つかった要素が番兵なのかどうかチェックする必要がある
2分探索
- 昇順や降順など規則的に並んだデータに対して使える
- 考え方探索対象のデータから、中央値を取得する(対象データを2つに分ける)目的のキーの値が中央値より大きいか小さいかで分けたデータの一方を探索対象にするまた同じように中央値を取得して、データを2つに分けて探索をするを繰り返す
- 終了条件探索キーの値と、中央値が一致する探索範囲がなくなる
- 2分探索はArrays.binarySerachで提供されている以下の変数を更新していって検索する探索範囲先頭のインデックス末尾のインデックス
  - 探索対象のデータから、中央値を取得する(対象データを2つに分ける)
  - 目的のキーの値が中央値より大きいか小さいかで分けたデータの一方を探索対象にする
  - また同じように中央値を取得して、データを2つに分けて探索をするを繰り返す
  - 探索キーの値と、中央値が一致する
  - 探索範囲がなくなる
  - 以下の変数を更新していって検索する探索範囲先頭のインデックス末尾のインデックス
  - 探索範囲先頭のインデックス
  - 末尾のインデックス
ハッシュ法
- 探索に加えてデータの追加削除を効率よく行う方法
- 値と要素数から剰余を算出する
- 剰余をインデックス値として配列にアクセスする
衝突とは
- データ追加にて18を追加したい剰余の6を取得する6には既に値が格納されている。という状態のこと
  - 18を追加したい剰余の6を取得する6には既に値が格納されている。という状態のこと
  - 剰余の6を取得する6には既に値が格納されている。という状態のこと
  - 6には既に値が格納されている。という状態のこと
衝突時の解決法
- チェイン法同一のハッシュ値をもつ要素を線形リストで管理する
- オープンアドレス法空きバケットが見つかるまでハッシュを繰り返す
  - 同一のハッシュ値をもつ要素を線形リストで管理する
  - 空きバケットが見つかるまでハッシュを繰り返す

2分探索コード(Arrays.binarySerach)

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

中央値と比べて以下のいずれかを選択してループする※中央値の値によって先頭か末尾を更新し続けるだけ

先頭インデックスを中央値＋1にする
末端インデックスを中央値－1にする

if (midVal < key)
    low = mid + 1;
else if (midVal > key)
    high = mid - 1;

Arrays.binarySerachの利用サンプル

int reuslt = Arrays.binarySearch(new int[]{1, 2, 3, 4},3
// 2

スタックキュー

スタック
- 最後に入れたデータが最初に取り出される
キュー
- 最初に入れたデータが最初に取り出される
プッシュ
- データを入れる
ポップ
- データを取り出す

再帰

再帰的アルゴリズムを利用

マージソート
クイックソート
2分探索木

階乗値の計算

public void test(){
        int result = factorial(4);
        System.out.println(result); // 24
    }

    private int factorial(int n){
        if(n > 0){
            // 再帰呼出し
            return n * factorial(n - 1);
        } else {
            // 終了条件
            return 1;
        }
    }

考え方

factorial(4)
4 * factorial(3)
- factorial(3)
- 3 * factorial(2)factorial(2)2 * factorial(1)factorial(1)1 * factorial(0)return 1;return 1 * factorial(0) →　1 * 1return 2 * factorial(1) →　2 * 1
- return 3 * factorial(2) →　3 * 2
  - factorial(2)
  - 2 * factorial(1)factorial(1)1 * factorial(0)return 1;return 1 * factorial(0) →　1 * 1
  - return 2 * factorial(1) →　2 * 1
  - factorial(1)
  - 1 * factorial(0)return 1;
  - return 1 * factorial(0) →　1 * 1
  - return 1;
return 4 * factorial(3) →　4 * 6

→ 4 * 3 * 2 * 1

ハノイの塔

ハノイの塔とは

https://www.p-game.jp/game237/

中間軸の出し方
- 軸番号1,2,3の合計6を起点に、6-x-y

public void test(){
        hanoi(3,1,3);
    }

    // ハノイの塔
    // no枚の円盤をxからyに移動する
    private void hanoi(int no, int x, int y){
        if(no > 1){
            hanoi(no - 1, x, 6 - x - y);
        }
        System.out.printf("円盤[%d]を%d軸から%d軸へ移動する\n", no, x, y);
        if(no > 1){
            hanoi(no - 1, 6 - x - y, y);
        }
    }

円盤[1]を1軸から3軸へ移動する
円盤[2]を1軸から2軸へ移動する
円盤[1]を3軸から2軸へ移動する
円盤[3]を1軸から3軸へ移動する
円盤[1]を2軸から1軸へ移動する
円盤[2]を2軸から3軸へ移動する
円盤[1]を1軸から3軸へ移動する

ソート

単純交換ソート(バブルソート)
- 先頭から昇順ソートする場合1つ後ろの値と比較して大きい場合は入れ替える
  - 1つ後ろの値と比較して大きい場合は入れ替える

public void testman(){
    int[] array = new int[]{5,3,4,7,8,2,9,6,1,0};
    sort(array);
}

private void sort(int[] array){
    for(int i = 0; i < array.length ; i ++){
        for(int j = array.length - 1 ; j > i ; j--){
            if(array[i] > array[j]){
                swap(array,i,j);
            }
        }
    }
}

private void swap(int[] array, int idx1, int idx2){
    int temp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = temp;
}

クイックソート
- 基準となる値を設定する
- 基準値より小さいグループと大きいグループにわけるそれぞれのグループで基準値を決める基準値より小さいグループと大きいグループに分ける繰り返し
- この繰り返しは再帰呼出しを行います
  - それぞれのグループで基準値を決める
  - 基準値より小さいグループと大きいグループに分ける繰り返し
  - 繰り返し

配列の分割

基準値を決めて、基準値より前と後ろで基準値以上の値と以下の値で分割する
- 以下の場合、中央のインデックス値を基準値にする
- 中央のイデックス値を起点に配列の分割を行うまだソートはされませんが、基準値起点で配列の大小分割される
  - まだソートはされませんが、基準値起点で配列の大小分割される

public void test(){
        int[] array = new int[]{6,3,5,0,9,1,2,7,8}; // pivot = 9
        quickSort(array,array.length);
    }

    // クイックソート(未完成)
    private void quickSort(int[] array,int length){
        int leftCursor = 0;
        int rightCursor = length - 1;
        // 基準値
        int pivot = array[(leftCursor + rightCursor) / 2]; //中央の要素

        // 左右のカーソルが交差したら終了
        while(leftCursor <= rightCursor){
            // 配列の前から走査する
            // 配列の前から、基準値より大きい要素を発見する
            //  → (大きい要素に当たるまで繰り返しています)
            // 発見した要素を特定するためにleftCursorをインクリメントする（その要素が格納されたインデックス値にする）
            while(array[leftCursor] < pivot) leftCursor++;
            // 配列の後ろから走査する
            // 配列の後ろから、基準値より小さい要素を発見する
            // 　→ (小さい要素に当たる前で繰り返しています)
            // 発見した要素を特定するためにrightCursorをデクリメントする(その要素が格納されたインデックス値にする)
            while(array[rightCursor] > pivot) rightCursor--;
            // お互いのカーソルの位置から
            //　例えば{3,4,8,5,35,7,8,6,9,0,1}の場合
            // leftCursorは2 rightCursorは10です
            //   8が7より大きい　1が7より小さい
            if(leftCursor <= rightCursor){
                // 配列の値を交換する
                swap(array, leftCursor++, rightCursor--);
                // 入れ替えたらカーソルを進める
                // 進めないと、whileの条件で抜けてループする
            }
        }
    }

    // 値の入れ替え
    private void swap(int[] array, int idx1, int idx2){
        int temp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = temp;
    }

基準値を起点に大小振り分けられていることがわかります。

再帰でソート

この処理を再帰的に繰り返せば完全なソートが完了します

public void test(){
        int[] array = new int[]{6,3,5,0,9,1,2,7,8}; // pivot = 9
        // 最初の呼び出しのカーソル位置は始点と終点です
        quickSort(array,0,array.length -1);
        System.out.println("sss");
    }

    // クイックソート
    // 引数でカーソル位置を受取るようにする
    private void quickSort(int[] array,int left, int right){
        int leftCursor = left;
        int rightCursor = right;
        // 基準値
        int pivot = array[(leftCursor + rightCursor) / 2]; //中央の要素

        // 左右のカーソルが交差したら終了
        while(leftCursor <= rightCursor){
            // 配列の前から走査する
            // 配列の前から、基準値より大きい要素を発見する
            //  → (大きい要素に当たるまで繰り返しています)
            // 発見した要素を特定するためにleftCursorをインクリメントする（その要素が格納されたインデックス値にする）
            while(array[leftCursor] < pivot) leftCursor++;
            // 配列の後ろから走査する
            // 配列の後ろから、基準値より小さい要素を発見する
            // 　→ (小さい要素に当たる前で繰り返しています)
            // 発見した要素を特定するためにrightCursorをデクリメントする(その要素が格納されたインデックス値にする)
            while(array[rightCursor] > pivot) rightCursor--;
            // お互いのカーソルの位置から
            //　例えば{3,4,8,5,35,7,8,6,9,0,1}の場合
            // leftCursorは2 rightCursorは10です
            //   8が7より大きい　1が7より小さい
            if(leftCursor <= rightCursor){
                // 配列の値を交換する
                swap(array, leftCursor++, rightCursor--);
                // 入れ替えたらカーソルを進める
                // 進めないと、whileの条件で抜けてループする
            }
        }
        // 右カーソルが始点位置より大きい間は繰り返す
        if(left < rightCursor){
            // 始点は常に0
            // 基準値より小さい値のみのエリアを再度ソートする
            quickSort(array,left,rightCursor);
        }
        // 左カーソルが終点位置より小さい間は繰り返す
        if(leftCursor < right){
            // 終点は常に最後の要素のインデックス
            // 基準値より大きい値のみのエリアを再度ソートする
            quickSort(array,leftCursor,right);
        }
    }

今回の再帰は戻り値がないので感覚が掴みやすいです

参考書籍

新・明解Javaで学ぶアルゴリズムとデータ構造

アルゴリズムの勉強１