Como determinar a complexidade temporal do algoritmo de ordenação bubble sort?

A complexidade temporal do algoritmo de ordenação bubble sort é determinada pelo número de comparações e permutações que realiza.

O bubble sort passa várias vezes pelo array, comparando elementos adjacentes em cada iteração e trocando-os de lugar se estiverem na ordem errada.

• Nos piores e médios casos, o algoritmo realiza aproximadamente n-1 passagens por um array de n elementos.
• Em cada passagem, ocorrem até n-1 comparações.

No total, a complexidade temporal é O(n²).

Exemplo:

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            std::swap(arr[j], arr[j + 1]);
        }
    }
}

Assim, o algoritmo não é eficiente para arrays grandes devido à sua complexidade quadrática.