Algoritmos | Clasificación | Pregunta 10

¿Cuál es la mejor complejidad temporal del tipo burbuja?

(A) N^2
(B) NlogN
(C) N
(D) N(logN)^2

Respuesta: (C)
Explicación: La ordenación de burbuja funciona mejor si se ordenan los datos de entrada. es decir, si los datos de entrada se ordenan en el mismo orden que la salida esperada. Esto se puede lograr usando una variable booleana. La variable booleana se usa para verificar si los valores se intercambian al menos una vez en el ciclo interno.
Considere el siguiente fragmento de código:

int main()
{   
    int arr[] = {10, 20, 30, 40, 50}, i, j, isSwapped;
    int n = sizeof(arr) / sizeof(*arr);
    isSwapped = 1;
    for(i = 0; i < n - 1 && isSwapped; ++i)
    {
        isSwapped = 0;
        for(j = 0; j < n - i - 1; ++j)
            if (arr[j] > arr[j + 1])
            {
                swap(&arr[j], &arr[j + 1]);
                isSwapped = 1;
            }
    }
    for(i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    return 0;
}

Tenga en cuenta que en el código anterior, el ciclo externo se ejecuta solo una vez.
Cuestionario de esta pregunta