// bubble_sort.cpp
// Glenn G. Chappell
// 9 Oct 2009
//
// For CS 311 Fall 2009
// Bubble Sort on an Array

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <algorithm>
using std::swap;


// bubbleSort
// Do Bubble Sort on a given array.
// Requirements on Types:
//     operator< must be a total order on T.
//     T must have a copy ctor and copy assignment.
// Pre:
//     p points to an array of at least n items of type T
// Post:
//     p[0 .. n-1] contains the same items as it did initially,
//      but now sorted by < (in a stable manner).
template <typename T>
void bubbleSort(T p[], int n)
{
    for (int pass = 1; pass <= n-1; ++pass)
        // Passes; exit when sorted
    {
        // Do one Bubble Sort pass on p[0 .. bubbleSize-1],
        //  that is, on pairs 0,1 up to bubbleSize-2,bubbleSize-1
        bool swapped = false;  // True if any swaps during this pass

        for (int i = 0; i < n-pass; ++i)
            // p[i], p[i+1] are current pair
        {
            // Compare & maybe swap p[i], p[i+1]
            if (p[i+1] < p[i])  // Out of order?
            {
                swap(p[i], p[i+1]);
                swapped = true;
            }
        }

        // If no swaps, then array is sorted; we're done
        if (!swapped)
            break;
    }
}


// main
// Test function bubbleSort on an array
int main()
{
    const int SIZE = 11;
    int arr[SIZE] = { 5, 3, 2, 8, 5, 9, 10, 4, 6, 1, -4 };
    bubbleSort(arr, SIZE);
    for (int i = 0; i < SIZE; ++i)
        cout << arr[i] << " ";
    cout << endl;
    cout << endl;

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}