// Bubble Sort 冒泡排序
//   时间：O(n^2) 最坏/平均
//         O(n) 最好
//   空间：O(1)
//   稳定：是
#include "common/sort_test.hpp"

void bubble_sort(std::vector<int> &a)
{
    const int n = static_cast<int>(a.size());
    for (int i = 0; i < n - 1; ++i)
    {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j)
        {
            if (a[j] > a[j + 1]) // 比较大小，如果该元素大于下一个元素就交换位置，得出的数组是升序的
            {
                std::swap(a[j], a[j + 1]);
                swapped = true; // 标记有交换操作
            }
        }
        if (!swapped)
            break; // 这一轮没有任何交换 ⇒ 已经有序，直接退出排序
    }
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return sort_test::run("Bubble Sort", bubble_sort, argc, argv);
}