BlogWonderHowTo

Clasificación (parte 5.0): clasificación por selección

En primer lugar, permítanme disculparme una vez más por ese error, que no logré advertir a tiempo.

Está bien, está bien … Suficiente enfurruñamiento, roble. ¡Hazlo!

El proceso detrás de la clasificación por selección

¡Hola gente de NB! Vamos a hablar de Orden de selección – ¡Ah, sí, vinculé Wikipedia!

La ordenación por selección se parece mucho a la ordenación por inserción, que, si puede recordar una publicación mía anterior, implica encontrar el elemento más pequeño en una matriz y moverlo a un lado, proceder a encontrar el siguiente elemento más pequeño, y así sucesivamente. , y así…

Pero el orden de selección, por el contrario, no cambia todo de los elementos; encuentra el elemento más pequeño a[i], donde sea que esté, y lo intercambia con cualquier elemento que ocupe actualmente a[0], a no ser que i == 0.

Continúa para encontrar el siguiente elemento más pequeño, excluyendo el nuevo a[0]. Podríamos llamar a esto a[j]. El algoritmo intercambia esto con a[1] a no ser que j == 1. Y esto continúa hasta que todos los elementos están en orden.

Imagen vía imgur.com

El algoritmo es O (n ^ 2) y O(norte). Este es el último complejidad cuadrática algoritmo de clasificación que pretendo cubrir.

Implementación de Ruby

Referirse a esta para el código fuente de mi implementación Ruby de Selection Sort. Alternativamente, se proporcionará una captura de pantalla a continuación.

Salte a la línea 9 en esa captura de pantalla porque no me voy a molestar en discutir la toma de entrada.

En primer lugar, observe el anidado por los bucles son lo que hace que este algoritmo O (n ^ 2) (inserte el odio a sí mismo sobre por error de bucle en la ordenación por inserción aquí).

Muy bien, comenzamos con el primer elemento, str[0]. Y seguimos adelante y asumimos que str[0] es el elemento más pequeño, porque todavía no hemos visto ningún elemento más pequeño en str. Pero solo almacenemos el posición de este elemento mínimo, 0. Por lo tanto, tenemos min_pos = i.

Así que ahora revisamos la matriz en el interior por bucle buscando un elemento más pequeño. No comenzaremos desde I porque eso sería tonto y redundante, ya que sabemos que el si condición dentro del bucle podría nunca evaluar como verdadero cuando i == j sin la interferencia divina de los dioses de la informática.

Si encontramos un elemento más pequeño, actualice min_pos para contener el índice de ese elemento. Una vez que hayamos pasado str, terminando el interior por, sabemos que hemos encontrado el elemento más pequeño entre I y el final de la matriz (n-1).

Si I no es la posición del elemento más pequeño en la porción sin clasificar de str, debemos intercambiar str[i] con str[min_pos], lo que significa que colocamos el elemento más pequeño de la parte aún sin clasificar de str (Nota: cualquier elemento a la izquierda de str[i] componen la porción ordenada de str) donde pertenece y tira el “original” str[i] en la única ranura disponible, str[min_pos], ya que el elemento más pequeño de la parte no ordenada se ha movido a la parte ordenada de la matriz.

Aquí hay una imagen:

Imagen vía blogspot.com

Y seguimos con este proceso hasta que hayamos pasado por la totalidad de str, haciendo todo de str parte de la porción clasificada.

Versión C ++

Aquíes el código para mi implementación C ++ de Selection Sort. Y una captura de pantalla aguarda a continuación:

Es fundamentalmente lo mismo que el código Ruby, semánticamente.

Examine los comentarios, pero creo que no tiene sentido explicar más este código, ya que hice un trabajo (con suerte) increíble arriba. Nota: lo que era str en el código Ruby es vec en el código C ++, porque yo … eh … no hay razón, de verdad.

Pitón

Sé que dije que usaría Ruby y C ++ exclusivamente para esta serie, pero el bueno de JSchmoe fue y transfirió los algoritmos a Python. Puedes encontrar sus porties de salida (broma de IRC [join #nullbyte !]) en pastebin aquí.

Conclusión

Eso es todo para la clasificación por selección, la última complejidad cuadrática algoritmo de clasificación que me propuse cubrir en esta serie.

Fue un placer
roble

¡PS Quicksort aún está por llegar!

Publicaciones relacionadas

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Botón volver arriba
Cerrar