ソート

#include <stdio.h>

void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }

/* バブルソート — O(n²)、安定
各ラウンドで最大要素を末尾に「バブル」させる */
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  /* 最適化：早期終了 */
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }
        if (!swapped) break;  /* 整列済みのため、早期終了 */
    }
}

/* クイックソートの分割関数 — 平均O(n log n)、不安定
基準pivotを選び、pivotより小さいものを左、大きいものを右に置く */
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  /* 最後の要素を基準として選ぶ */
    int i = low - 1;        /* i は pivot より小さい領域の末尾を指す */
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);  /* 基準を正しい位置に置く */
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  /* 分割インデックス */
        quickSort(arr, low, pi - 1);   /* 左半分を再帰的にソート */
        quickSort(arr, pi + 1, high);  /* 右半分を再帰的にソート */
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = 7;
    bubbleSort(arr1, n1);
    printf("バブルソート: "); printArray(arr1, n1);
    /* 出力: 11 12 22 25 34 64 90 */

    int arr2[] = {64, 34, 25, 12, 22, 11, 90};
    quickSort(arr2, 0, 6);
    printf("クイックソート: "); printArray(arr2, 7);
    /* 出力: 11 12 22 25 34 64 90 */
    return 0;
}