//Maxwell Brewer                 CS1A                     Chapter 8, p. 488,  #9
//
/*******************************************************************************
 * SORTING BENCHMARKS
 * _____________________________________________________________________________
 * This program will compare the efficiency of Bubble Sort and Selection Sort
 * by counting the number of exchanges each algorithm makes when sorting the
 * same list of numbers.
 * _____________________________________________________________________________
 * INPUT
 *   None (The array of numbers is predefined).
 * 
 * OUTPUT
 *   The number of exchanges made by each sorting algorithm.
 *
 ******************************************************************************/

#include <iostream>
using namespace std;

// Bubble Sort function definition
int bubbleSort(int arr[], int size)
{
    int count = 0; // Counter for number of exchanges

    // Bubble Sort algorithm
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // Swap adjacent elements if they are in the wrong order
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                count++; // Increment exchange count
            }
        }
    }

    return count;
}

int selectionSort(int arr[], int size)
{
    int pos, count = 0; // Variables to store minimum position
                        // and exchange count

    // Selection Sort algorithm
    for (int i = 0; i < size - 1; i++)
    {
        pos = i; // Assume the current element is the minimum

        for (int j = i + 1; j < size; j++)
        {
            if (arr[pos] > arr[j])
                pos = j; // Update position of minimum element
        }

        // Swap elements if a new minimum is found
        if (pos != i)
        {
            int temp = arr[i];
            arr[i] = arr[pos];
            arr[pos] = temp;
            count++; // Increment exchange count
        }
    }

    return count;
}

int main()
{
    // Initialize arrays with identical values for fair comparison
    int arr [] = {1, 4, 6, 2, 3, 7, 8, 5, 12, 18, 14,
                 19, 9, 15, 10, 11, 20, 13, 17, 16};
                 
    int arr1[] = {1, 4, 6, 2, 3, 7, 8, 5, 12, 18, 14,
                 19, 9, 15, 10, 11, 20, 13, 17, 16};
    int n = 20;

    // Call sorting functions and display the number of exchanges for each
    cout << "\nThe number of exchanges made in Bubble Sort is: " 
         << bubbleSort(arr, n);
         
    cout << "\n\nThe number of exchanges made in Selection Sort is: " 
         << selectionSort(arr1, n);

    return 0;
}