探索

1. 二分探索

前提条件：配列は事前に昇順にソートされていること

基本概念：目的値と中央要素を比較して探索範囲を半分にする

アルゴリズム手順

• 初期化処理：
  1. left = 0;
  2. right = 配列長 - 1;
  3. pivot = left + (right - left)/2;
• left <= right の間繰り返す
  1. arr[pivot] と target を比較する
  2. target == arr[pivot] → pivot を返却
  3. target > arr[pivot] → left = pivot + 1;
  4. target < arr[pivot] → right = pivot - 1;

計算量

• 時間計算量：O(log N)
• 空間計算量：O(1)

public static int searchElement(int[] data, int target) {
    int start = 0;
    int end = data.length - 1;
    int middle = start + (end - start) / 2;
    
    while (start <= end) {
        if (target == data[middle]) {
            return middle;
        } else if (target > data[middle]) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
        middle = start + (end - start) / 2;
    }
    return -1;
}

ソート

- バブルソート - 稳定性あり

アルゴリズム概要：

隣接する要素を比較し、前者が後者より大きい場合は入れ替える。この操作を n-1 回繰り返す。

public int[] bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
    return array;
}

- 選択ソート - 穩定性なし

アルゴリズム概要：

未ソート部分から最小値を選び、その位置に挿入する。

public int[] selectionSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        if (i != minIndex) {
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
    return array;
}

- 挿入ソート

アルゴリズム概要：

最初の要素を既にソート済みとし、残りの要素を順次適切な位置に挿入していく。

public int[] insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i;
        while (j > 0 && key < array[j - 1]) {
            array[j] = array[j - 1];
            j--;
        }
        if (i != j) {
            array[j] = key;
        }
    }
    return array;
}

- クイックソート

アルゴリズム概要：

基準値（ピボット）を選択し、それより小さい要素は左側、大きいものは右側に分ける。その後再帰的に各部分をソートする。

public void quickSortExample() {
    int[] numbers = {16, 1, 0, 9, 8};
    numbers = quickSort(numbers, 0, numbers.length - 1);
    for (int num : numbers) {
        System.out.println(num);
    }
}

private int[] quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
    return arr;
}

private int partition(int[] arr, int low, int high) {
    int pivot = low;
    int index = pivot + 1;
    for (int i = index; i <= high; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}