#include <avr/io.h>
#include <util/delay.h>

// Initialize UART for communication at a specified baud rate
void init_uart(unsigned int baud) {
    unsigned int ubrr = F_CPU / 16 / baud - 1;  // Calculate the baud rate register value
    UBRR0H = (unsigned char)(ubrr >> 8);        // Set the high byte of UBRR
    UBRR0L = (unsigned char)ubrr;                // Set the low byte of UBRR
    UCSR0B = (1 << TXEN0);                       // Enable the transmitter
    UCSR0C = (1 << UCSZ01) | (1 << UCSZ00);      // Set frame format to 8 data bits, 1 stop bit
}

// Send a single character over UART
void send_char(unsigned char c) {
    while (!(UCSR0A & (1 << UDRE0)));  // Wait until the transmit buffer is empty
    UDR0 = c;                          // Send the character
}

// Send a string over UART
void send_string(const char *str) {
    while (*str) {
        send_char(*str++);  // Send each character one by one
    }
}

// Convert an integer to string and send it over UART
void send_int(int num) {
    char buffer[10];  
    itoa(num, buffer, 10);  // Convert integer to string
    send_string(buffer);    // Send the string representation
}

// Bubble Sort algorithm to sort an array
void bubble_sort(int arr[], int size) {
    int i, j, temp;
    for (i = 0; i < size - 1; i++) {
        send_string("Pass ");
        send_int(i + 1);
        send_string(":\n");

        for (j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap if elements are in the wrong order
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }

        // Print array after the pass
        send_string("Array after pass: ");
        for (int k = 0; k < size; k++) {
            send_int(arr[k]);
            if (k < size - 1) send_char(',');
        }
        send_char('\n');
    }
}

int main(void) {
    init_uart(9600);  // Initialize UART at 9600 baud rate

    // Define the array to be sorted
    int arr[10] = {34, 12, 5, 6, 78, 9, 55, 1, 4, 20};

    // Print the initial array
    send_string("Initial Array: ");
    for (int i = 0; i < 10; i++) {
        send_int(arr[i]);
        if (i < 9) {
            send_char(',');  // Separate elements with a comma
        }
    }
    send_char('\n');

    // Perform bubble sort on the array
    bubble_sort(arr, 10);

    // Print the sorted array
    send_string("Sorted Array: ");
    for (int i = 0; i < 10; i++) {
        send_int(arr[i]);
        if (i < 9) {
            send_char(',');
        }
    }
    send_char('\n');

    return 0;  // End of program
}