// bubble_sort2.cpp
// Glenn G. Chappell
// 3 Mar 2008
//
// For CS 311 Spring 2008
// Bubble Sort
// Version #2: Using Forward Iterators


#include <iostream>
using std::cout;
using std::endl;
#include <algorithm>  // for std::iter_swap


// bubbleSort
// Do Bubble Sort on a given range.
// Requirements on Types:
//     FDIter must be a forward iterator type.
//     operator< must be a total order on the value type of FDIter.
//     The value type of FDIter must have a copy ctor and copy assignment.
// Pre:
//     [first, last) is a valid range.
// Post:
//     [first, last) contains the same items as it did initially,
//      but now sorted by < (in a stable manner).
template <typename FDIter>
void bubbleSort(FDIter first, FDIter last)
{
    while (first != last)
    {
        bool didSwap = false;  // True if any swaps during this pass

        // Do one Bubble Sort pass on range [first, last).
        // Iterator "last" goes down one at the end of each pass.
        FDIter iter1 = first;  // *iter1, *iter2 are current pair
        FDIter iter2 = first;
        ++iter2;
        while (iter2 != last)
        {
            // compare & maybe swap *iter1, *iter2
            if (*iter2 < *iter1)
            {
                //std::swap(*iter1, *iter2);
                std::iter_swap(iter1, iter2);
                didSwap = true;
            }

            // Move current pair to next pair
            iter1 = iter2;
            ++iter2;
        }

        // If no swaps, sorted; we're done
        if (!didSwap)
            break;

        // set last to its new value
        last = iter1;
    }
}


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