#include <iostream>
#include <list>
#include <stdlib.h>
#include <time.h>

#define SWAP_INT(a,b) {a = a ^ b; b = a ^ b; a = a ^ b;}

using namespace std;

void init_int_list(list<int> &data, int n)
{
    for (int i = 0; i < n; ++i)
        data.push_back(rand()%10);
}

void print_int_list(list<int> &data)
{
    list<int>::iterator it = data.begin();
    for (it = data.begin(); it != data.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

bool check(list<int> &data, list<int> &data_backup)
{
    int sum = 0, sum2 = 0;
    list<int>::iterator it = data.begin();
    list<int>::iterator it2 = ++(data.begin());
    for (; it2 != data.end(); ++it, ++it2)
    {
        sum += *it;
        if (*it2 < *it)
            return false;
    }
    sum += *it;
    for (it = data_backup.begin(); it != data_backup.end(); ++it)
        sum2 += *it;
    if (sum != sum2)
        return false;
    return true;
}

void bubble(list<int> &a)
{   
    int i;
    int length = a.size();
    list<int>::iterator it = a.begin();
    list<int>::iterator it2 = ++(a.begin());
    for (i = 0; i < length-1; ++i)
        for (it = a.begin(), it2 = ++(a.begin()); it2 != a.end(); ++it, ++it2)
            if (*it > *it2)
                SWAP_INT(*it, *it2)
}

// 增加一个变量判断是否已经有序
void bubble2(list<int> &a)
{
    int i;
    bool complete;
    int length = a.size();
    list<int>::iterator it = a.begin();
    list<int>::iterator it2 = ++(a.begin());

    for (i = 0; i < length-1; ++i)
    {
        complete = true;
        for (it = a.begin(), it2 = ++(a.begin()); it2 != a.end(); ++it, ++it2)
        {
            if (*it > *it2)
            {
                SWAP_INT(*it, *it2)
                complete = false;
            }
        }
        if(complete)
            break;
    }
}

int main(void)
{
	// 目测一次排序结果
    list<int> a;
    srand(time(NULL));
    init_int_list(a, 12);

    print_int_list(a);
    //bubble(a); //
    bubble2(a); //
    print_int_list(a);


    // 多次验证排序结果是否正确
    for(int i = 0; i < 300; ++i)
    {
        list<int> data, data_backup;
        init_int_list(data, 12);
        data_backup.assign(data.begin(), data.end());
        bubble2(data);
        if (!check(data, data_backup))
        {
            cout << "error:" << endl << "Original data:" << endl;
            print_int_list(data_backup);
            cout << "Sorted data:" << endl;
            print_int_list(data);
            return EXIT_FAILURE;
        }
    }
    cout << "check" << endl;

    return EXIT_SUCCESS;
}