¿Qué es el tipo de selección?

Echa un vistazo: Tutorial de selección de video en codewhoop

1. La ordenación por selección es un algoritmo de ordenación basado en la comparación simple en el lugar.
2. En este método dividimos la matriz en dos sub-matrices: ordenada (izquierda) sin clasificar (derecha)
3. Inicialmente consideramos que la matriz completa no está ordenada.
4. Seleccione el elemento más a la izquierda en la submatriz sin clasificar y cámbielo por el elemento más pequeño en la submatriz sin clasificar.

Para mí, esta es la forma más fácil de entender el concepto de selección.

En esta imagen, la primera línea representa la matriz original sin clasificar.

Comenzamos en el índice 0 y, por defecto, lo llamamos el mínimo. Entonces, el mínimo en este mismo paso es 35.

Ahora, recorra la matriz y encuentre el valor MÁS PEQUEÑO en la matriz. Son las 17. Cambia las 35 y las 17.

17 fue el valor más pequeño, por lo que se colocó en la matriz en su lugar correcto intercambiando con 35.

Ahora, escanee la nueva matriz en busca del valor SIGUIENTE MÁS PEQUEÑO. [La línea de paréntesis que tengo debajo de los números delinea los únicos números que necesito tener en cuenta cuando busco el siguiente mínimo más pequeño porque el resto de la matriz ya está en su lugar y el primer número en el paréntesis será el número que se cambiará el mínimo con.

Ahora en la línea 2, mirando solo los números con la línea debajo de ellos, encuentre el número más pequeño. Entonces lo cambiamos por 27 con 79 porque 79 es el primer número en el paréntesis.

Ahora en la línea 3, intercambie 38 con 34 porque 34 es el mínimo.

Ahora en la línea 4, intercambie 76 con el mínimo en el conjunto que es 35.

Sigue haciendo esto hasta que todo esté ordenado.

Un algoritmo O (n ^ 2) que no aprovecha el orden existente (es decir, no adaptativo).

Las comparaciones se calculan por n (n + 1) / 2, que para n grande hace que esto no sea adecuado.

Es estable La mejor opción sería InsertionSort, que también es estable y adaptativa. Su complejidad también es la misma, pero para pequeñas n (unos 32 elementos), es maravillosamente rápido.

Pésimo rendimiento en tiempo constante

Para a, 0, n-1 {

Para b, a + 1, n {

Si a (b)

Intercambiar a (), a, b}

El mejor algoritmo de clasificación para enseñar y el peor algoritmo para usar en aplicaciones prácticas. Está en su lugar los algoritmos de clasificación y comienza por encontrar el más pequeño de la matriz e intercambiarlo con el primer elemento de la matriz. Luego verifica el elemento más pequeño en la submatriz a partir del segundo elemento y así sucesivamente. La complejidad del tiempo es O (n ^ 2) y la complejidad del espacio es O (1)

El orden de selección es un orden de comparación in situ.
El algoritmo divide la matriz de entrada en dos partes:
1: la submatriz de elementos ya ordenados, que se construye de izquierda a derecha, y
2: la submatriz de elementos que quedan por clasificar que ocupan el resto de la matriz.
Inicialmente, el subconjunto ordenado está vacío y el subconjunto sin ordenar es la matriz de entrada completa. El algoritmo continúa encontrando el elemento más pequeño en el subarreglo no ordenado, intercambiándolo con el elemento sin clasificar más a la izquierda (colocándolo en orden ordenado) y moviendo los límites del subarreglo un elemento a la derecha.

Puede acceder al código y a los ejemplos en este enlace: Algoritmo de ordenación: ordenación por selección

En el orden de selección, seleccionamos progresivamente el valor más pequeño (o más grande) de una lista de [matemática] n [/ matemática], [matemática] n-1 [/ matemática], [matemática] n-2 [/ matemática], [ elementos matemáticos] n-3 [/ matemáticos], hasta que la longitud de la lista llegue a cero. El algoritmo consta de los siguientes dos pasos:

1. Seleccione el elemento más pequeño (o más grande) de la lista y muévalo al final de la lista.
2. Repita el proceso con [matemática] n-1 [/ matemática], [matemática] n [/ matemática], [matemática] n-1 [/ matemática], [matemática] n-2 [/ matemática], [matemática] n -3 … [/ math] elementos y así sucesivamente hasta que la longitud de la lista sea cero.

Las comparaciones son siempre entre los elementos sin clasificar (que se muestran en azul arriba). Con [math] n [/ math] elementos sin clasificar, tendrías n-1 comparaciones. Con n-1 elementos sin clasificar, tendría comparaciones n-2 y así sucesivamente. Entonces el número total de comparaciones es:

[matemáticas] (n-1) + (n-2) + (n-3) + ……… + 1 = \ frac {n (n-1)} {2} \ aprox n ^ 2. [/ matemáticas]

Por lo tanto, la complejidad de la operación de comparación es [matemática] O (n ^ 2). [/ Matemática]

En el peor de los casos, el número de intercambios para elementos [math] n [/ math] sería [math] n-1. [/ math] Por lo tanto, la complejidad de la operación de intercambio es [math] O (n) [/ math].

Dado que el orden de un problema es el máximo de sus operaciones constituyentes, la complejidad general es [matemática] O (n ^ 2) [/ matemática].

Respuesta corta: encuentre el elemento más pequeño en su matriz al revisarlos todos. Agregue ese elemento a su salida y elimínelo de la matriz. Repita este proceso hasta que todos los elementos se hayan agregado a la salida.

Respuesta más larga: cualquier tipo que siga la lógica anterior debe considerarse alguna variante del tipo de selección. La implementación más típica funciona en el lugar dividiendo la matriz en una porción ordenada (salida) y una porción no ordenada. Inicialmente, la matriz completa no está ordenada, pero si ya se han agregado K elementos a la salida, los índices 0- (K-1) son la salida hasta el momento, y los índices K- (longitud-1) no están clasificados. Para agregar el siguiente elemento a la salida, debe escanear la sección no ordenada, seleccionar el elemento más pequeño y colocarlo en la siguiente posición de salida, índice K. El elemento que estaba previamente en ese índice se mueve a donde solía estar el elemento seleccionado. ser.

“El algoritmo de selección ordena una matriz al encontrar repetidamente el elemento mínimo (considerando el orden ascendente) de [la] parte sin clasificar y ponerlo al principio. El algoritmo mantiene dos submatrices en una matriz determinada “.

Para obtener más información, consulte Selección de clasificación – GeeksforGeeks.

(Texto citado de Selección de selección – GeeksforGeeks).

Es un algoritmo de clasificación O (n) = n ^ 2.

Busca el mínimo y lo intercambia con la primera celda de una matriz

luego busca el mínimo desde la segunda celda y reemplaza

con la segunda celda. Por inducción busca el mínimo de

la enésima celda y la reemplaza con la enésima celda.

Digamos que tiene una baraja de cartas que desea ordenar. Para este ejemplo, permitamos que un ♠ tenga un valor más alto que un ♥ que tiene un valor más alto que un ♦ que es aún más alto que un ♣ de la misma carta. Finalmente, permita que los Ases sean bajos, menos valiosos que un 2.

Para la selección, seleccionaremos el mazo, seleccionaremos la carta que estamos buscando y la colocaremos en su ubicación final ordenada. Por ejemplo, si tuviéramos que ordenar las cartas en orden descendente, sabemos que la primera carta debe ser ♠ Rey. Revisaremos el mazo sin clasificar hasta que encontremos esa carta. Cuando lo hagamos, sáquelo del mazo sin clasificar y colóquelo como la primera carta en el mazo ordenado. Tenga en cuenta que el Rey ♠ está en su ubicación final. Será la primera carta en el mazo cuando cualquier otra carta descienda después de ella. Ve a través del mazo sin clasificar buscando ♥ King, luego ♦ King y así sucesivamente.

Se puede aplicar el mismo principio a los números, encontrar el número entero más grande de la lista, extraerlo y luego encontrar el siguiente más grande y así sucesivamente.