Complejidad del tiempo de ordenación por inserción

Complejidad Del Tiempo De Ordenacion Por Insercion



Considere los siguientes números:

50 60 30 10 80 70 20 40







Si esta lista se ordena en orden ascendente, sería:



10 20 30 40 50 60 70 80



Si se ordena en orden descendente, sería:





80 70 60 50 40 30 20 10

La clasificación por inserción es un algoritmo de clasificación que se utiliza para clasificar la lista en orden ascendente o descendente. Este artículo trata solo de la clasificación en orden ascendente. Ordenar en orden descendente sigue la misma lógica dada en este documento. El objetivo de este artículo es explicar el ordenamiento por inserción. La programación se realiza en el siguiente ejemplo en C. El ordenamiento por inserción se explica aquí usando una matriz.



Algoritmo para la ordenación por inserción

Se da una lista desordenada. El objetivo es ordenar la lista en orden ascendente utilizando la misma lista. Se dice que ordenar una matriz no ordenada usando la misma matriz es ordenar en el lugar. Aquí se utiliza la indexación basada en cero. Los pasos son los siguientes:

    • La lista se explora desde el principio.
    • Mientras se lleva a cabo el escaneo, cualquier número menor que su predecesor se intercambia con su predecesor.
    • Este intercambio continúa a lo largo de la lista, hasta que ya no es posible intercambiar.
    • Cuando el escaneo llega al final, la clasificación está completa.

Ilustración de clasificación por inserción

Cuando se trata de la complejidad del tiempo, normalmente se tiene en cuenta el peor de los casos. El peor arreglo para la lista anterior es:

80 70 60 50 40 30 20 10

Hay ocho elementos con índices de cero a 7.

En el índice cero, el escaneo va a 80. Este es un movimiento. Este movimiento es una operación. Hay un total de una operación hasta el momento (un movimiento, sin comparación y sin intercambio). El resultado es:

| 80 70 60 50 40 30 20 10

En el índice uno, hay un movimiento a 70. 70 se compara con 80. 70 y 80 se intercambian. Un movimiento es una operación. Una comparación es también una operación. Un swap es también una operación. Esta sección proporciona tres operaciones. Hay un total de cuatro operaciones hasta ahora (1 + 3 = 4). El resultado es el siguiente:

70 | 80 60 50 40 30 20 10

En el índice dos, hay un movimiento a 60. 60 se compara con 80, luego se intercambian 60 y 80. 60 se compara con 70, luego se intercambian 60 y 70. Un movimiento es una operación. Dos comparaciones son dos operaciones. Dos swaps son dos operaciones. Esta sección proporciona cinco operaciones. Hay un total de nueve operaciones hasta ahora (4 + 5 = 9). El resultado es el siguiente:

60 70 | 80 50 40 30 20 10

En el índice tres, hay un movimiento a 50. 50 se compara con 80, luego se intercambian 50 y 80. 50 se compara con 70, luego se intercambian 50 y 70. 50 se compara con 60, luego se intercambian 50 y 60. Un movimiento es una operación. Tres comparaciones son tres operaciones. Tres swaps son tres operaciones. Esta sección proporciona siete operaciones. Hay un total de dieciséis operaciones hasta el momento (9 + 7 = 16). El resultado es el siguiente:

50 60 70 | 80 40 30 20 10

En el índice cuatro, hay un movimiento a 40. 40 se compara con 80, luego se intercambian 40 y 80. 40 se compara con 70, luego se intercambian 40 y 70. 40 se compara con 60, luego se intercambian 40 y 60. 40 se compara con 50, luego 40 y 50 se intercambian. Un movimiento es una operación. Cuatro comparaciones son cuatro operaciones. Cuatro swaps son cuatro operaciones. Esta sección proporciona nueve operaciones. Hay un total de veinticinco operaciones hasta el momento (16 + 9 = 25). El resultado es el siguiente:

40 50 60 70 80 | 30 20 10

En el índice cinco, hay un movimiento a 30. 30 se compara con 80, luego se intercambian 30 y 80. 30 se compara con 70, luego se intercambian 30 y 70. 30 se compara con 60, luego se intercambian 30 y 60. 30 se compara con 50, luego se intercambian 30 y 50. 30 se compara con 40, luego se intercambian 30 y 40. Un movimiento es una operación. Cinco comparaciones son cinco operaciones. Cinco swaps son cinco operaciones. Esta sección proporciona once operaciones. Hay un total de treinta y seis operaciones hasta el momento (25 + 11 = 36). El resultado es el siguiente:

30 40 50 60 70 80 | 20 10

En el índice seis, hay un movimiento a 20. 20 se compara con 80, luego se intercambian 20 y 80. 20 se compara con 70, luego se intercambian 20 y 70. 20 se compara con 60, luego se intercambian 20 y 60. 20 se compara con 50, luego 20 y 50 se intercambian. 20 se compara con 40, luego se intercambian 20 y 40. 20 se compara con 30, luego 20 y 30 se intercambian. Un movimiento es una operación. Seis comparaciones son seis operaciones. Seis swaps son seis operaciones. Esta sección proporciona trece operaciones. Hay un total de cuarenta y nueve operaciones hasta el momento (36 + 13 = 49). El resultado es el siguiente:

20 30 40 50 60 70 80 | 10

En el índice siete, hay un movimiento a 10. 10 se compara con 80, luego se intercambian 10 y 80. 10 se compara con 70, luego se intercambian 10 y 70. 10 se compara con 60, luego se intercambian 10 y 60. 10 se compara con 50, luego se intercambian 10 y 50. 10 se compara con 30, luego se intercambian 10 y 40. 10 se compara con 30, luego se intercambian 10 y 30. 10 se compara con 20, luego se intercambian 10 y 20. Un movimiento es una operación. Siete comparaciones son siete operaciones. Siete swaps son siete operaciones. Esta sección proporciona quince operaciones. Hay un total de sesenta y cuatro operaciones hasta el momento (49 + 15 = 64). El resultado es el siguiente:

10 20 30 40 50 60 70 80 10 |

¡El trabajo está hecho! Participaron 64 operaciones.

64 = 8x8 = 8 2

Complejidad de tiempo para la ordenación por inserción

Si hay n elementos para ordenar con la ordenación por inserción, el número máximo de operaciones posibles sería n2, como se demostró anteriormente. La complejidad del tiempo de ordenación por inserción es:

En 2 )

Esto usa la notación Big-O. La notación Big-O comienza con O en mayúscula, seguida de paréntesis. Dentro de los paréntesis está la expresión para el máximo número posible de operaciones.

Codificando en C

Al comienzo del escaneo, el primer elemento no puede cambiar su posición. El programa es esencialmente el siguiente:

    #incluir

void inserciónOrdenar ( int A [ ] , int N ) {
        por ( En t i = 0 ; i < NORTE; yo ++ ) {
intj = yo;
            tiempo ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
temperatura interna = A [ j ] ; A [ j ] = un [ j- 1 ] ; A [ j- 1 ] = temperatura; // intercambio
j--;
            }
        }
    }

 
La definición de función de inserciónSort() utiliza el algoritmo como se describe. Tenga en cuenta las condiciones para el ciclo while. Una función principal de C adecuada para este programa es:

int principal ( intargc, char ** argv )
    {
entero n = 8 ;
int A [ ] = { 50 ,   60 , 30 ,   10 ,   80 ,   70 ,   20 ,   40 } ;

tipo de inserción ( Un ) ;

        por ( En t i = 0 ; i < norte; yo ++ ) {
            imprimir ( '%i ' , A [ i ] ) ;
        }
        imprimir ( ' \norte ' ) ;

        devolver 0 ;
    }

 

Conclusión

La complejidad de tiempo para la ordenación por inserción se da como:

En 2 )

Es posible que el lector haya oído hablar de una complejidad de tiempo en el peor de los casos, una complejidad de tiempo en un caso promedio y una complejidad de tiempo en el mejor de los casos. Estas variaciones de la complejidad del tiempo de ordenación por inserción se analizan en el siguiente artículo de nuestro sitio web.