template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void BubbleSort2(T* x) {
    for (int i = 0; i < n; i++) {
        bool sorted = true;
        for (int j = n-1; j > i; j-- ) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                sorted = false;
            }
        }
        if (sorted) break;
    }
}