selection sort java selection sort algorithm examples
Este tutorial explicará todo sobre la clasificación de selección en Java junto con el algoritmo de clasificación de selección, el código Java, la implementación en Java y los ejemplos de Java:
La técnica de clasificación por selección es un método en el que se selecciona el elemento más pequeño de la matriz y se intercambia con el primer elemento de la matriz. A continuación, el segundo elemento más pequeño de la matriz se intercambia con el segundo elemento y viceversa.
=> Consulte aquí para ver los tutoriales de capacitación de la A a la Z de Java aquí.
Lo que vas a aprender:
Ordenar por selección en Java
De esta manera, el elemento más pequeño de la matriz se selecciona repetidamente y se coloca en su posición correcta hasta que se ordena toda la matriz.
Se mantienen dos submatrices para la clasificación por selección:
- Submatriz ordenada: En cada iteración, el elemento mínimo se encuentra y se coloca en su posición adecuada. Esta submatriz está ordenada.
- Submatriz sin clasificar: Los elementos restantes que no están ordenados.
La clasificación por selección es una técnica de clasificación sencilla y sencilla. La técnica solo implica encontrar el elemento más pequeño en cada pasada y colocarlo en la posición correcta. El ordenamiento por selección es ideal para conjuntos de datos más pequeños, ya que ordena el conjunto de datos más pequeño de manera eficiente.
Por lo tanto, podemos decir que la ordenación por selección no es aconsejable para listas de datos más grandes.
Algoritmo de clasificación por selección
El algoritmo general para el ordenamiento por selección se proporciona a continuación:
Orden de selección (A, N)
Paso 1 : Repita los pasos 2 y 3 para K = 1 a N-1
Paso 2 : Llamar a la rutina más pequeña (A, K, N, POS)
Paso 3 :
Cambiar A (K) por A (POS)
(Fin del ciclo)
Paso 4 : SALIDA
Rutina más pequeña (A, K, N, POS)
Paso 1 : (initialize) set smallestItem = A (K)
Paso 2 : (inicializar) establecer POS = K
Paso 3 :
para J = K + 1 a N -1, repita
si el elemento más pequeño> A (J)
establecer SmallItem = A (J)
establecer POS = J
(si termina)
(Fin del ciclo)
Paso 4 : devolver POS
Como puede ver, la rutina para encontrar el número más pequeño se llama mientras se recorre el conjunto de datos. Una vez que se encuentra el elemento más pequeño, se coloca en la posición deseada.
linux encuentra la diferencia entre dos archivos
Pseudocódigo para ordenar por selección
El pseudocódigo para el algoritmo de clasificación de selección se proporciona a continuación.
|_+_|Ilustremos ahora la ordenación de una matriz mediante ordenación por selección.
Ejemplo de clasificación de selección
Considere la siguiente matriz que se va a ordenar como un ejemplo de ordenación por selección.
A continuación se muestra una representación tabular de la ilustración:
| Lista sin clasificar | Elemento menor | Lista ordenada |
|---|---|---|
| {17,10,7,29,2} | 2 | {} |
| {17,10,7,29} | 7 | {2} |
| {17,10,29} | 10 | {2,7} |
| {17,29} | 17 | {2,7,10) |
| {29} | 29 | {2,7,10,17} |
| {} | {2,7,10,17,29} |
En la ilustración, vemos que con cada pasada, el siguiente elemento más pequeño se coloca en su posición correcta en la matriz ordenada. En general, para ordenar una matriz de N elementos, necesitamos N-1 pases en total.
Implementación de clasificación de selección en Java
Ahora demostremos el programa Java para implementar la ordenación por selección.
|_+_|Producción:
Matriz original: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Matriz ordenada: (2, 5, 7, 10, 15, 20, 23, 34, 42)
En el ejemplo de Java anterior, encontramos repetidamente el elemento más pequeño de la matriz y lo colocamos en la matriz ordenada hasta que toda la matriz esté completamente ordenada.
Selección Ordenar lista vinculada en Java
A continuación se muestra una lista vinculada y tenemos que ordenarla usando la clasificación de selección. Para hacer esto usaremos el enfoque recursivo de ordenamiento por selección. En lugar de intercambiar la parte de datos del nodo, intercambiaremos los nodos y realinearemos los punteros.
Entonces, si la lista vinculada se da de la siguiente manera:
A continuación se muestra el programa Java que implementa la clasificación anterior.
|_+_|Producción:
Lista vinculada original:
7 9 3 5 1 11
Lista vinculada después de ordenar:
1 3 5 7 9 11
Tenga en cuenta que en el programa anterior, hemos realineado los enlaces de los nodos en lugar de ordenar solo el componente de datos del nodo.
Preguntas frecuentes
P # 1) ¿Cómo funciona la clasificación por selección?
Responder: La clasificación por selección funciona manteniendo dos submatrices. El elemento mínimo del subarreglo sin clasificar se coloca en su posición adecuada en un subarreglo ordenado. Luego, el segundo elemento más bajo se coloca en su posición adecuada. De esta forma, toda la matriz se ordena seleccionando un elemento mínimo durante cada iteración.
Q #2) ¿Cuál es la complejidad del tipo de selección?
fusionar ordenamiento recursivo c ++
Responder: La complejidad general del orden de selección es O (n2), lo que lo convierte en el algoritmo ineficaz en conjuntos de datos más grandes. Otras técnicas de clasificación son más eficientes.
Q #3) ¿Cuáles son las ventajas y desventajas del tipo de selección?
Responder: La clasificación por selección es la técnica de clasificación en el lugar y, por lo tanto, no requiere almacenamiento adicional para almacenar elementos intermedios.
Funciona de manera eficiente en estructuras de datos más pequeñas, así como en los conjuntos de datos que están casi ordenados.
La principal desventaja de la técnica de clasificación por selección es que funciona muy mal a medida que aumenta el tamaño de la estructura de datos. No solo se vuelve más lento sino que también disminuye la eficiencia.
Q #4) ¿Cuántos intercambios hay en el orden de selección?
Responder: La técnica de clasificación por selección toma el número mínimo de intercambios. En el mejor de los casos, cuando se ordena la matriz, el número de intercambios en la ordenación de selección es 0.
Q #5) ¿La ordenación por selección es más rápida que la ordenación por inserción?
Responder: La clasificación por inserción es más rápida, eficiente y estable. La clasificación por selección es más rápida solo para conjuntos de datos más pequeños y estructuras parcialmente ordenadas.
Conclusión
La ordenación por selección es una técnica que funciona seleccionando el elemento mínimo mientras se recorre la matriz. Para cada pasada / iteración, se selecciona el siguiente elemento mínimo del conjunto de datos y se coloca en su posición adecuada.
La técnica de ordenación por selección funciona de manera eficiente cuando el número de elementos del conjunto de datos es menor, pero comienza a funcionar mal a medida que aumenta el tamaño del conjunto de datos. Se vuelve ineficaz en comparación con otras técnicas similares como la ordenación por inserción.
En este tutorial, hemos implementado ejemplos para ordenar matrices y listas vinculadas usando la ordenación por selección.
=> Visite aquí para ver la serie de formación Java para todos.
Lectura recomendada
- Cómo ordenar una matriz en Java - Tutorial con ejemplos
- Orden de selección en C ++ con ejemplos
- Tutorial de longitud de matriz de Java con ejemplos de código
- Método MongoDB Sort () con ejemplos
- Matriz irregular en Java - Tutorial con ejemplos
- Comando de ordenación de Unix con sintaxis, opciones y ejemplos
- Invertir una matriz en Java: 3 métodos con ejemplos
- Tutorial de JAVA para principiantes: más de 100 tutoriales prácticos en vídeo de Java