#include<iostream.h>
#define SIZE 5

// void swap( int & x, int & y )
// input: two referenced integers
// output: swaps the two integers
// return: none
void swap( int & x, int & y )
{
    int tmp = x;
    x = y;
    y = tmp;
}

// void print_arr( int arr[] )
// input: an array
// output: ouputs the contents with spaces seperating elements
// return: none
void print_arr( const int arr[] )
{
    for ( int i = 0 ; i < SIZE ; i++ )
        cout << arr[i] << " ";
    cout << endl;
}

// sort from low to high
int main()
{
    int arr[SIZE] = { 5, 3, 1, 2, 4 };
    // bubble sort
    for( int i = 0 ; i < ( SIZE - 1 ) ; i++ )
    {
        // each pass the highest remaining is in place
        for( int j = 0 ; j < ( SIZE - 1 ) ; j++ )
        {
            // compare adjacent
            if ( arr[j] > arr[j+1] )
                swap( arr[j], arr[j+1] );
        }
    }
    print_arr( arr );
    // insertion sort
    arr[0] = 5; arr[1] = 3; arr[2] = 1; arr[3] = 2; arr[4] = 4;
    for( int i = 0 ; i < SIZE ; i++ )
    {
        int low = arr[i];
        int j = i;
        //only look at sorted and one other element
        while (( j > 0 ) && ( low < arr[j-1] ))
        {
            arr[j] = arr[j-1];  // shift it right
            j--;
        }
        arr[j] = low;
    }
    print_arr( arr );
    // selection sort
    arr[0] = 5; arr[1] = 3; arr[2] = 1; arr[3] = 2; arr[4] = 4;
    for( int i = 0 ; i < ( SIZE - 1 ) ; i++ )
    {
        int mark = i;
        // find the lowest, each pass start at the next
        for( int j = i+1 ; j < SIZE ; j++ )
        {
            if ( arr[j] < arr[mark] )
                mark = j;
        }
        if ( mark != i )
        {
            swap( arr[mark], arr[i] );
        }
    }
    print_arr( arr );
    return 0;
}