Inserción Ordena la complejidad del tiempo

Considere los siguientes números:

50 60 30 10 80 70 20 40

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

10 20 30 40 50 50 60 70 80

Si se clasifica en orden descendente, sería:

80 70 60 50 40 30 20 20 10

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

Algoritmo para el tipo de inserción

Se da una lista sin clasificar. El objetivo es ordenar la lista en orden ascendente utilizando la misma lista. Se dice que clasificar una matriz sin clasificar con la misma matriz está clasificando en el lugar. La indexación basada en cero se usa aquí. Los pasos son los siguientes:

• • La lista se escanea desde el principio.
  • Mientras el escaneo continúa, 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 de inserción

Al lidiar con la complejidad del tiempo, es el peor caso que normalmente se tiene en cuenta. El peor acuerdo para la lista anterior es:

80 70 60 50 40 30 20 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. Hasta ahora hay un total de una operación (un movimiento, sin comparación y sin intercambio). El resultado es:

| 80 70 60 50 40 30 20 20 10

En el índice uno, hay un movimiento a 70. 70 se compara con 80. Se intercambian 70 y 80. Un movimiento es una operación. Una comparación también es una operación. Un intercambio también es 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 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 20

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 cambian 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 ahora (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 cambian 40 y 70. 40 se compara con 60, luego se cambian 40 y 60. 40 se compara con 50, luego se cambian 40 y 50. 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 ahora (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 comparan con 70, luego se intercambian 30 y 70. 30 se compara con 60, luego se intercambian 30 y 60. 30 se comparan 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 ahora (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 se intercambian 20 y 50. 20 se compara con 40, luego se intercambian 20 y 40. 20 se compara con 30, luego se intercambian 20 y 30. 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 ahora (36 + 13 = 49). El resultado es el siguiente:

20 30 40 50 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 ahora (49 + 15 = 64). El resultado es el siguiente:

10 20 30 40 50 50 60 70 80 10 |

El trabajo está hecho! 64 operaciones estaban involucradas.

64 = 8 x 8 = 8²

Complejidad del tiempo para el tipo de inserción

Si hay N. La complejidad del tiempo de clasificación de inserción es:

En²)

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 es la expresión para el número máximo posible de operaciones.

Codificación en C

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

#incluir
Void InsertionSort (int a [], int n)
para (int i = 0; iint j = i;
mientras (a [j] < A[j-1] && j-1 >= 0)
int temp = a [j]; A [j] = a [j-1]; A [j-1] = temp; //intercambio
J--;

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

int main (int argc, char ** argv)

int n = 8;
int a [] = 50, 60, 30, 10, 80, 70, 20, 40;
Insercionsort (a, n);
para (int i = 0; iprintf ("%i", a [i]);

printf ("\ n");
regresar 0;

Conclusión

La complejidad del tiempo para el tipo de inserción se da como:

En²)

El lector podría haber oído hablar de una complejidad de tiempo peor, la complejidad del tiempo promedio y la complejidad del tiempo en el mejor de los casos. Estas variaciones de la complejidad del tiempo de clasificación de inserción se discuten en el próximo artículo en nuestro sitio web.