Complejidad del tiempo de clasificación de selección

El orden de selección es una especie de algoritmo de clasificación. Una lista no organizada se puede clasificar en orden ascendente o en orden descendente. Considere la lista sin clasificar:

55 65 35 15 85 75 25 45

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

15 25 35 45 55 65 75 85

Si la lista se ordene en orden descendente, sería:

85 75 65 55 45 35 25 15

En este artículo, solo se considera la clasificación en orden ascendente. Clasificación de la selección buscando elementos pequeños y intercambiándolos con los elementos iniciales, comenzando desde el elemento más pequeño, mientras que los elementos iniciales reemplazados se vuelven ascendentes. Una lista debe ordenarse en orden ascendente al final de este proceso.

El artículo tiene como objetivo determinar la complejidad del tiempo del tipo de selección. La siguiente programación se realiza en el lenguaje C.

Algoritmo de clasificación de selección

Los pasos para el orden de selección son los siguientes:

• Suponga que el primer elemento es el elemento más pequeño.
• Compare este elemento con los otros elementos para conocer el verdadero elemento más pequeño.
• Intercambie el elemento más pequeño encontrado con el primer elemento.
• Repita los tres pasos anteriores en orden, excluyendo el primer elemento reemplazado.
• Continuar repitiendo los tres pasos anteriores, excluyendo los elementos hacia el extremo izquierdo (inferior) que ha sido reemplazado.
• La clasificación termina cuando se alcanza el último elemento.

Aquí hay dos tipos de operación principales, que son comparación e intercambio. Pasar de un elemento a otro también es una operación, pero lleva relativamente poco tiempo en comparación con la operación de comparación o la operación de intercambio en el tipo de selección.

En²) Complejidad del tiempo

Considere el siguiente código:

int resultado = 0;
para (int i = 0; i<8; i++)
para (int j = 0; j<8; j++)
resultado = resultado + 1;


printf ("%i \ n", resultado);

Hay un bucle externo e interno. Cada bucle itera ocho veces. La operación de adición única para ambos bucles es la operación principal y opera 64 veces. 64 = 8 x 8 = 82. La salida es 64.

Se considera que este código tiene 82 operaciones principales. Si 8 es reemplazado por N, entonces la complejidad del tiempo se daría como:

En 2)

Esto usa la notación Big-O. La notación comienza con O en mayúscula, seguida de paréntesis. Dentro de la paréntesis es el número de operaciones principales para el código.

Considere el siguiente código:

int resultado = 0;
para (int i = 0; i<8; i++)
para (int j = i; j<8; j++)
resultado = resultado + 1;


printf ("%i \ n", resultado);

El bucle exterior itera ocho veces. El bucle interno itera hasta la octava vez, pero comienza desde i, que es el número de iteración del bucle exterior. La salida es 36. La operación de adición única funciona 36 veces y no 64 veces. Bueno, esto todavía se considera como O (N2) complejidad del tiempo. El funcionamiento del orden de selección es similar a este código. En otras palabras, se considera que el tipo de selección tiene complejidad de tiempo O (N2).

Codificación en C

El tipo de selección siempre dará complejidad de tiempo o (n2). No importa cómo se organizan los elementos de la matriz. Esto se debe a que todos los elementos se escanean primero; Luego, el resto de los elementos sin los primeros se escanean a continuación; escaneo del resto de los elementos sin los dos primeros seguidores, y así sucesivamente. El escaneo debe completarse antes de intercambiar.

La lista para clasificar es:

P o i u y t r e w q

El programa C clasifica en orden ascendente. Esencialmente, el programa comienza con:

#incluir
void selectiosort (char a [], int n)
para (int i = 0; iint minindx = i;
para (int j = i+1; jif (a [j] < A[minIndx])
minindx = j;

char temp = a [i]; A [i] = a [minindx]; A [minindx] = temp; // intercambio

Se incluye la biblioteca responsable de la entrada del teclado y la salida al monitor. Luego, existe la definición de la función de clasificación de selección. Esta función como parámetros tiene la matriz (referencia) con la lista y el número de elementos en la matriz.

Hay dos bucle para los bucle; uno está anidado dentro del otro. El bucle for-bucle externo sobre todos los elementos que comienzan desde el primero. Mientras que el bucle for-boL de Forer está en un índice, el bucle interno de For-Loop itera sobre el resto de los elementos, excluyendo el elemento anterior. La operación principal es la operación de comparación en el bucle anidado.

El intercambio se realiza por cada iteración del bucle exterior justo después de que se complete el bucle interno.

Una función principal C adecuada para el programa es:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'p', 'o', 'i', 'u', 'y', 't', 'r', 'e', ​​'w', 'q';
selectioSort (a, n);
para (int i = 0; iprintf ("%c", a [i]);
printf ("\ n");
regresar 0;

La salida es:

E i o p q r t u w y

ordenado.

Comienza con la declaración del número de elementos en la matriz. Luego está la Declaración de la matriz. Hay diez elementos en la matriz. Estos elementos son personajes. Entonces, la declaración de matriz comienza con "char". A continuación, se llama la función de clasificación de inserción. El primer argumento de la llamada de función es el nombre de la matriz. El segundo argumento es el número de elementos en la matriz.

Sigue un for-bucle. Este bucle imprime los personajes ordenados. Utiliza la función printf () del stdio.H Biblioteca. El primer argumento de esta función es una cadena. Esta cadena es una cadena especial pero aún tiene caracteres que se imprimirían. También tiene parámetros para argumentos. En este caso, solo hay un parámetro, %C. También hay solo un argumento, un [i]. Después de que todos los caracteres se hayan impreso en una línea, la siguiente función printf () lleva la salida a la siguiente línea.

Conclusión

Este artículo discutió los pasos para el tipo de selección, que incluyen asumir que el primer elemento es el elemento más pequeño, comparando este elemento con el resto de los elementos y conocer el verdadero elemento más pequeño. Además, un usuario necesita intercambiar el elemento más pequeño encontrado con el primer elemento y repetir los tres pasos anteriores en orden, excluyendo el primer elemento reemplazado. Los últimos pasos incluyen continuar repitiendo los tres pasos anteriores, excluyendo los elementos hacia el extremo izquierdo (inferior) que han sido reemplazados; La clasificación termina cuando se alcanza el último elemento. La complejidad del tiempo para el tipo de selección es O (N2).