#include <iostream>
using namespace std;

//Written by Hudson Bielstein for Exam 3.

void arrayContents(int array[], const int SIZE)
{
    for ( int i = 0; i < SIZE; i++ )
    {
        cout << array[i] << " ";
        
        if ( i == (SIZE/2) )
            cout << endl;
    }
}

 

int bubbleSort(int array[], const int SIZE)
{
    int swaps, temp;
    bool swap;
    
    do
    {
        swap = false;
        
        for ( int i = 0; i < (SIZE-1); i++ )
        {
            if ( array[i+1] < array[i] )
            {
                temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
                swap = true;
                swaps++;
            }
        }
        
    } while ( swap == true );
    
    cout << "Done!\n\n";
    cout << "-Contents of Array 1 After Bubble Sorting-\n";
    arrayContents(array, SIZE);
    cout << endl << endl;
    
    return swaps;
}

 

int selectionSort(int array[], const int SIZE)
{
    int swaps = 0, smallest, smallIndex;
    
    for ( int i = 0; i < SIZE; i++ )
    {
        smallest = array[i];
        smallIndex = i;
        
        for ( int j = i+1; j < SIZE; j++ )
        {
            if ( array[j] < smallest )
            {
                smallest = array[j];
                smallIndex = j;
            }
        }
        
        array[smallIndex] = array[i];
        array[i] = smallest;
        swaps++;
    }
    
    cout << "Done!\n";
    cout << endl;
    cout << "-Contents of Array 2 After Selection Sorting-\n";
    arrayContents(array, SIZE);
    cout << endl << endl;
    
    return swaps;
}

 

int main()
{
    cout << "Written by Hudson Bielstein for Exam 3.\n\n";
    
    const int SIZE = 20;
    int array1[SIZE] = { 4, 1, 38, 24, 25, 84, 90, 9, 1, 3,
                         3, 86, 63, 2, 12, 120, 119, 100, 18, 20 },
        array2[SIZE] = { 4, 1, 38, 24, 25, 84, 90, 9, 1, 3,
                         3, 86, 63, 2, 12, 120, 119, 100, 18, 20 };
    int swaps1, swaps2;
    
    
    cout << "-Contents of Array 1 Before Sorting-\n";
    arrayContents(array1, SIZE);
    cout << endl << endl;
    
    cout << "-Contents of Array 2 Before Sorting-\n";
    arrayContents(array2, SIZE);
    cout << endl << endl;
    
    cout << "Sending Array 1 to be Bubble Sorted...";
    swaps1 = bubbleSort(array1, SIZE);
    
    cout << "Sending Array 2 to be Selection Sorted...";
    swaps2 = selectionSort(array2, SIZE);
    
    cout << "The Bubble Sort moved numbers " << swaps1 << " times to sort the array, \n";
    cout << "while the Selection Sort only swapped numbers " << swaps2 << " times.\n";
    cout << "Clearly Selection Sort is more efficient than Bubble Sort.";
    
    return 0;
}