Сколько проходов нужно для пузырьковой сортировки?

Question

Как проверить количество проходов для сортировки элемента в массиве с помощью пузырьковой сортировки? У меня уже есть наивное решение.

int count_the_pass(int *p,int size){
    int count;
    for(int i = 0;i<size-1;i++){
        bool flag = false;
        for(int j=0;j<size-i-1;j++){
            if(p[j]>p[j+1]){
                int temp = p[j];
                p[j] = p[j+1];
                p[j+1] = temp;
                flag = true;
            }
        }
        if(flag==false)
            return i;
    }
}

Однако этот метод, подходящий только для размера массива, достаточно мал (менее 3000).
Когда размер массива большой, у меня превышено ограничение по времени. Как можно рассчитать количество проходов для большей эффективности?

Я также пытался подсчитать число инверсий всего массива. Но я не могу понять, каково отношение числа инверсии и числа проходов.
Пример:

{1,3,4,2} Инверсия {{3,2), (4,2)} и требует двух проходов.

{1,4,2,3} Инверсия: {(4,2), (4,3)} и требуется один проход.

Оба из двух В примерах 2 пары инверсии, но для первого нужно 2 прохода для сортировки, для второго - только один проход.