// Timothy Price				CS1A				Ch 8 Challenge 10
/******************************************************************************
 * Compare sorting algorithm progress
 * 
 * This program sorts two arrays using bubble sort and selection sort, 
 * displaying the progress as each array is sorted
 * 
 * Inputs:
 *  Two identical arrays of 8 unsorted integers
 * 
 * Outputs:
 *  Initial array contents
 *  Array state after each pass of bubble sort
 *  Array state after each pass of selection sort
 *****************************************************************************/

#include <iostream>

using namespace std;

// Function Prototypes
void bubbleSort(int arr[], int size);
void selectionSort(int arr[], int size);
void printArray(const int arr[], int size);

int main() {
    const int SIZE = 8;

    // Two identical arrays of 8 integers
    int array1[SIZE] = {34, 12, 55, 3, 29, 41, 18, 7};
    int array2[SIZE] = {34, 12, 55, 3, 29, 41, 18, 7};

    // Display first array and run Bubble Sort
    cout << "Original First Array (for Bubble Sort):" << endl;
    printArray(array1, SIZE);
    
    cout << endl << "Bubble Sort Progress (After Each Pass):" << endl;
    bubbleSort(array1, SIZE);

    cout << endl << "----------------------------------------" << endl << endl;

    // Display second array and run Selection Sort
    cout << "Original Second Array (for Selection Sort):" << endl;
    printArray(array2, SIZE);
    
    cout << endl;
    cout << "Selection Sort Progress (After Each Pass):" << endl;
    selectionSort(array2, SIZE);

    return 0;
}

// Function Definitions

// Bubble sort modified to print array contents after each pass
void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // Print contents after completion of the current pass
        cout << "After Pass " << (i + 1) << ": ";
        printArray(arr, size);
    }
}

// Selection sort modified to print array contents after each pass
void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        // Print contents after completion of the current pass
        cout << "After Pass " << (i + 1) << ": ";
        printArray(arr, size);
    }
}

// Helper function to print the array
void printArray(const int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}