#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 9

// Hàm tạo mảng với giá trị ngẫu nhiên từ 1 đến 9
void CREATE(int a[], int n) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 9 + 1;
    }
}

// Hàm in mảng
void IN(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// Bubble Sort
void BUBBLE_SORT(int a[], int n) {
    printf("\n--- Bubble Sort ---\n");
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        printf("Bước %d: ", i + 1);
        IN(a, n);
    }
}

// Selection Sort
void SELECT_SORT(int a[], int n) {
    printf("\n--- Selection Sort ---\n");
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
        printf("Bước %d: ", i + 1);
        IN(a, n);
    }
}

// Insertion Sort
void INSERT_SORT(int a[], int n) {
    printf("\n--- Insertion Sort ---\n");
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
        printf("Bước %d: ", i);
        IN(a, n);
    }
}

// Hàm main
int main() {
    int a[N], b[N], c[N];

    CREATE(a, N);

    // Sao chép mảng để dùng cho các thuật toán khác nhau
    for (int i = 0; i < N; i++) {
        b[i] = c[i] = a[i];
    }

    printf("Mảng ban đầu: ");
    IN(a, N);

    BUBBLE_SORT(a, N);
    SELECT_SORT(b, N);
    INSERT_SORT(c, N);

    return 0;
}