ソートアルゴリズムを改めて勉強してみた

はじめに

ちょっとアルゴリズムが苦手なことに気づき始めたので、改めて勉強。
Geminiに内容とソースを貰い、脳内シミュレーションをして理解していく。

お世話になったサイト

勉強中ソートアルゴリズム

バブルソート

隣同士を比較して、順番を入れ替えていく。

From Gemini

void bubleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

選択ソート

先頭から順に最小値を探して位置を入れ替えていく。

From Gemini

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

挿入ソート

1個目をソート済と考えて、2個目以降をソート済と比較して、適切な位置に入れていく。
途中に入れる場合は、ズラシていく。

From gemini

void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        // 適切な位置にkeyを挿入
        arr[j + 1] = key;
    }
}

クイックソート

基準値を決めて、基準値より小さいグループ、大きいグループに分けていく。
それを小さく繰り返していく。

From Gemini

void quickSort(int[] arr, int left, int right) {

    IO.print("quickSort - start - left: " + left + ", right: " + right + "\n");

    if (left >= right)
        return;

    // 1. 分割（パーティション）
    int pivot = arr[left + (right - left) / 2]; // 真ん中の要素をピボットにする
    int index = partition(arr, left, right, pivot);

    IO.print("quickSort - after partition - pivot: " + pivot + ", index: " + index + "\n");

    for (int num : arr) {
        IO.print(num + " ");
    }
    IO.print("\n");
    // 2. 左右のグループに対して再帰的に実行
    quickSort(arr, left, index - 1);
    quickSort(arr, index, right);
}

int partition(int[] arr, int left, int right, int pivot) {
    while (left <= right) {
        IO.print("partition - left: " + left + ", right: " + right + "\n");
        // ピボットより小さい間、左ポインタを進める
        while (arr[left] < pivot)
            left++;
        // ピボットより大きい間、右ポインタを戻す
        while (arr[right] > pivot)
            right--;

        // 見つかったら左右を入れ替える
        if (left <= right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    IO.print("partition - final left: " + left + ", final right: " + right + "\n");
    return left;
}

マージソート

グループを１つになるまで分けていく。
１つまで分けたグループを整列しながら結合していく。

ヒープソート

親子の木構造を作って、親 ＞＝子 の関係を維持するように入れ替えていって、親を確定（＝一番大きい値）
で、また、親 ＞＝子 の関係を維持するように入れ替えを繰り返す。