配列の基本アルゴリズムコード集

1. 配列のソート

1.1 バブルソート

配列の要素を並べ替えるためには、バブルソート、挿入ソート、クイックソートなどのアルゴリズムが利用可能です。バブルソートは初心者にも理解しやすく、重要なアルゴリズムの一つです。

昇順ソートの実現方法：

  1. 隣接する要素を比較し、前の方が大きい場合は位置を交換します。
  2. 配列の最初から最後まで、隣接要素の比較と交換を繰り返します。このステップが完了すると、配列の最後の要素が最大の要素になります。
  3. 上記の手順を配列の全要素に対して繰り返しますが、最終要素は除外します。
  4. 比較する要素の数を逐次減らし、要素の交換が発生しなくなるまで繰り返します。

バブルソートの特徴は、各ループごとに最大の要素が配列の最後に移動し、次回のループではその要素を除外する点です。


import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = { 3, 6, 2, 4, 8, 12, 7, 9 };
        System.out.println(Arrays.toString(arr));

        int count = 0;
        boolean isSorted = true;

        for (int i = 0, n = arr.length; i < n - 1; i++) {
            count++;
            isSorted = true;

            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    isSorted = false;
                }
            }

            if (isSorted) {
                break;
            }
        }

        System.out.println("比較回数：" + count); // 比較回数：3
        System.out.println(Arrays.toString(arr)); // [2, 3, 4, 6, 7, 8, 9, 12]
    }
}

1.2 Arraysツールの利用

Javaの標準ライブラリには配列のソート機能が含まれています。配列を並べ替える際には、Arrays.sort()メソッドを利用できます。


public class Main {
    public static void main(String[] args) {
        int[] arr = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };

        System.out.println("ソート前：" + Arrays.toString(arr));
        Arrays.sort(arr);
        System.out.println("ソート後：" + Arrays.toString(arr));
    }
}

1.3 小節

  • 代表的なソートアルゴリズムにはバブルソート、挿入ソート、クイックソートがあります。
  • バブルソートは2つのループ構造を利用して配列を並べ替えます。
  • Javaの標準ライブラリであるArrays.sort()を利用することで簡単にソートできます。
  • 配列のソートは元の配列を直接変更します。

2. 配列要素の検索

2.1 無序配列の検索

無序配列の要素検索は、配列を直接探索するか、Arraysツールを利用して行うことができます。

2.1.1 配列探索

整数配列の場合：


int[] arr = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
int searchValue = 36;
int index = -1;

for (int i = 0; i < arr.length; i++) {
    if (arr[i] == searchValue) {
        index = i;
        break;
    }
}

System.out.println("検索値：" + searchValue + "、インデックス：" + index);

文字列配列の場合：


String[] singerArr = { "李荣浩", "盘尼西林", "王菲", "王贰浪", "鹿先森乐队", "孙燕姿", "G.E.M.邓紫棋", "方大同", "品冠儿子" };
String searchValue = "方大同";
int index = -1;

for (int i = 0; i < singerArr.length; i++) {
    if (singerArr[i].equals(searchValue)) {
        index = i;
        break;
    }
}

2.1.2 双指針探索

整数配列の場合：


int[] arr = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
int searchValue = 36;
int index = -1;

for (int i = 0, k = arr.length - 1; i <= k; i++, k--) {
    if (arr[i] == searchValue) {
        index = i;
        break;
    }
    if (arr[k] == searchValue) {
        index = k;
        break;
    }
}

System.out.println("検索値：" + searchValue + "、インデックス：" + index);

文字列配列の場合：


String[] singerArr = { "李荣浩", "盘尼西林", "王菲", "王贰浪", "鹿先森乐队", "孙燕姿", "G.E.M.邓紫棋", "方大同", "品冠儿子" };
String searchValue = "方大同";
int index = -1;

for (int i = 0, k = singerArr.length - 1; i <= k; i++, k--) {
    if (singerArr[i].equals(searchValue)) {
        index = i;
        break;
    }
    if (singerArr[k].equals(searchValue)) {
        index = k;
        break;
    }
}

2.2 有序配列の検索

有序配列の要素検索には、ArraysツールのbinarySearch()メソッドを利用できます。


public class Main {
    public static void main(String[] args) {
        int[] arr = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
        int value = 36;

        Arrays.sort(arr);
        int index = Arrays.binarySearch(arr, value);

        System.out.println("検索値：" + value + "、インデックス：" + index);
    }
}

2.3 二分検索

二分検索は、有序配列での要素検索に非常に効率的なアルゴリズムです。

二分検索の手順：

  1. 検索対象の配列の中央要素と目標要素を比較します。
  2. 中央要素と目標要素が一致した場合、検索成功です。
  3. 中央要素が目標要素より小さい場合、後半部分を検索対象とします。
  4. 中央要素が目標要素より大きい場合、前半部分を検索対象とします。

public class Main {
    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 };
        int value = 37;
        int index = -1;
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == value) {
                index = mid;
                break;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        System.out.println("検索値：" + value + "、インデックス：" + index);
    }
}

2.4 小節

  • 配列の要素検索は、無序配列と有序配列の2種類があります。
  • 無序配列の検索は直接探索かArraysツールを利用します。
  • 有序配列の検索は二分検索アルゴリズムを利用します。

3. 配列のシャッフル

配列のシャッフルは、ランダムな順序に並べ替えることを指します。

Fisher-Yates洗牌アルゴリズム（Knuth洗牌アルゴリズム）を利用します。

3.1 実現方法

  1. シャッフル対象の配列Pを準備します。
  2. 配列Pの未シャッフル部分からランダムな要素を選択します。
  3. 選択した要素を配列Pの未シャッフル部分の最後の要素と交換します。
  4. 上記手順を繰り返し、配列Pの全要素をシャッフルします。

int[] arr = { 1, 2, 3, 4, 5, 6, 7 };

for (int n = arr.length; n > 0; n--) {
    int index = (int) (Math.random() * n);
    int temp = arr[index];
    arr[index] = arr[n - 1];
    arr[n - 1] = temp;
}

System.out.println(Arrays.toString(arr));

4. 配列の回転

配列の回転は、音楽プレイヤーのプレイリストのような機能を実現します。

4.1 左回転

左回転を2回行った例：

原始配列：[1, 2, 3, 4, 5, 6, 7, 8]

1回目：[2, 3, 4, 5, 6, 7, 8, 1]

2回目：[3, 4, 5, 6, 7, 8, 1, 2]


public void rotateLeft(int w, int[] arr) {
    int length = arr.length;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < length - 1; j++) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

4.2 右回転

右回転を2回行った例：

原始配列：[1, 2, 3, 4, 5, 6, 7, 8]

1回目：[8, 1, 2, 3, 4, 5, 6, 7]

2回目：[7, 8, 1, 2, 3, 4, 5, 6]


public void rotateRight(int w, int[] arr) {
    int length = arr.length;
    for (int i = 0; i < w; i++) {
        for (int j = length - 1; j > 0; j--) {
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
        }
    }
}

タグ: Java 配列 ソート 検索 シャッフル

7月14日 02:15 投稿

ホットタグ

©2026 異端開発室