Los siguientes ejercicios corregidos se relacionan con los algoritmos de clasificación: clasificación por selección, clasificación por inserción, clasificación por burbuja, clasificación cóctel, clasificación rápida y clasificación por fusión.
Ordenaciones iterativas: ordenar por selección
En una matriz de n elementos (numerados de 0 a n-1), el principio de clasificación por selección es el siguiente:
- busque el elemento más pequeño de la matriz e intercámbielo con el elemento de índice 0;
- busque el segundo elemento más pequeño de la matriz e intercámbielo con el elemento del índice 1;
- continúe de esta manera hasta que la matriz esté completamente ordenada.
En pseudocódigo, el algoritmo se escribe de la siguiente manera:
En cualquier caso, para ordenar no elementos, ordenar por selección realiza n(n-1)/2 comparaciones, por lo tanto en O(n²).
Ordenaciones iterativas: ordenación por inserción
La ordenación por inserción es una algoritmo clasificación clásica. La mayoría de la gente lo usa naturalmente para clasificar los naipes.
La ordenación por inserción considera cada elemento de la matriz y lo inserta en el lugar correcto entre los elementos ya ordenados. Así, cuando se considera un elemento, los elementos que le preceden ya están ordenados, mientras que los elementos que le siguen aún no están ordenados.
Para encontrar el lugar donde insertar un elemento entre los anteriores, se debe comparar con estos últimos, y desplazarlos para liberar un lugar donde realizar la inserción. El desplazamiento ocupa el espacio que deja libre el elemento considerado. En la práctica, estas dos acciones se realizan en una sola pasada, que consiste en “elevar” el elemento a medida que avanza hasta encontrar un elemento más pequeño.
Aquí hay un ejemplo para entender mejor el principio en la pizarra [6, 5, 3, 1, 8, 7, 2, 4].
Aquí está su pseudocódigo:
La complejidad de la ordenación por inserción es O (n²) en el peor de los casos y lineal en el mejor de los casos. En el peor de los casos, que se alcanza cuando la matriz se ordena al revés, el algoritmo realiza alrededor de n²/2 asignaciones y comparaciones; Si la matriz ya está ordenada, hay n-1 comparaciones y como máximo n asignaciones.
Ordenaciones iterativas: ordenación de burbuja
Bubble sort o spread sort es un algoritmo de clasificación. Consiste en comparar repetidamente los elementos consecutivos de un arreglo, e intercambiarlos cuando están mal ordenados. Debe su nombre al hecho de que mueve rápidamente los elementos más grandes al final de la pintura, como burbujas de aire que subirían rápidamente a la superficie de un líquido.
El algoritmo itera a través de la matriz y compara elementos consecutivos. Cuando dos elementos consecutivos no están en orden, se intercambian.
Después de un primer escaneo completo de la matriz, el elemento más grande está necesariamente al final de la matriz, en su posición final. De hecho, tan pronto como se encuentra el elemento más grande durante el recorrido, está mal clasificado en relación con todos los elementos siguientes, por lo que se intercambia con el siguiente hasta llegar al final del recorrido.
Después de la primera ejecución, estando el elemento más grande en su posición final, ya no es necesario procesarlo. El resto de la pintura, sin embargo, todavía está desordenado. Por lo tanto, debe ser atravesado nuevamente, deteniéndose en el penúltimo elemento. Tras esta segunda hilada, los dos elementos mayores se encuentran en su posición definitiva. Por tanto, es necesario repetir los recorridos de la mesa, hasta colocar los dos elementos más pequeños en su posición final.
Una optimización común de esta clasificación consiste en interrumpirla tan pronto como se realiza un recorrido de los elementos posiblemente todavía desordenados (bucle interno) sin permutación. En efecto, esto significa que se ordena toda la matriz. Esta optimización requiere una variable adicional.
Es posible poner un While en lugar del primer For. En este caso, es necesario incrementar i dentro del ciclo y ya no necesita el descanso.
Para la clasificación no optimizada, la complejidad del tiempo es O(n²), siendo n el tamaño de la matriz.
Para una clasificación optimizada, el número de iteraciones del ciclo externo está entre 1 y n. De hecho, podemos demostrar que después del i-ésimo paso, los últimos i elementos del arreglo están en su lugar. En cada iteración, hay exactamente n-1 comparaciones y, como máximo, n-1 permutaciones.
El peor de los casos (n iteraciones) se alcanza cuando el elemento más pequeño está al final de la matriz. La complejidad es entonces O(n²). El mejor de los casos (una sola iteración) se alcanza cuando la matriz ya está ordenada. En este caso, la complejidad es lineal.
Clasificación iterativa: clasificación de cócteles
La clasificación de cócteles, la clasificación de coctelera o la clasificación de burbuja bidireccional es una variante de la clasificación de burbuja1 que es tanto un algoritmo de clasificación como una clasificación de comparación. La diferencia entre este algoritmo y la ordenación de burbujas es que realiza una ordenación en cada dirección en cada paso a lo largo de la lista que se va a ordenar.
Este algoritmo de ordenación es solo un poco más difícil de entender e implementar que la ordenación de burbujas, y resuelve parcialmente el problema de las tortugas de la ordenación de burbujas (las tortugas son los elementos pequeños cerca del final de la lista original, que retroceden muy lentamente, una ubicación por vez). iteración, hacia su ubicación final).
Durante el primer paso, el primer recorrido a la derecha mueve elementos más grandes que su vecino inmediato a la derecha y, en particular, moverá el elemento más grande de la lista paso a paso a su ubicación final al final de la lista. Luego, el segundo escaneo a la izquierda moverá los elementos más pequeños que su vecino inmediato a la izquierda y, en particular, moverá el elemento más pequeño de la lista a su ubicación final en la parte superior de la lista. a la izquierda. Del mismo modo, durante la segunda pasada, el segundo elemento más grande y el segundo elemento más pequeño se unirán a su vez en su ubicación final, y así sucesivamente.
Después de que pasa i, los primeros elementos i y los últimos elementos i están en su ubicación final. Por lo tanto, ya no necesitan ser verificados. Por lo tanto, es posible optimizar este algoritmo comprobando en cada paso solo la parte central de la lista que aún no se ha ordenado definitivamente. Esto permite reducir a la mitad el número de comparaciones a realizar.
Un derivado del tipo burbuja es el tipo cóctel o tipo coctelera. Este método de clasificación se basa en la siguiente observación: en la clasificación de burbuja, los elementos pueden avanzar rápidamente hasta el final de la matriz, pero solo se mueven al principio de la matriz una posición a la vez.
La idea de la selección de cócteles es alternar la dirección del viaje. Obtenemos una ordenación un poco más rápida, por un lado porque requiere menos comparaciones, por otro lado porque vuelve a leer los datos más recientes en el momento del cambio de dirección (por lo tanto, todavía están en la memoria caché). Sin embargo, el número de permutaciones a realizar es idéntico. Así, el tiempo de ejecución es siempre proporcional a n², por lo tanto mediocre.
La complejidad del peor de los casos y del mejor de los casos en O(.) es la misma que la clasificación de burbuja.
Ordenaciones recursivas: ordenación rápida
Quicksort es un algoritmo de clasificación por comparación, su funcionamiento es bastante simple de entender y se usa ampliamente en entradas grandes. De hecho, tiene una complejidad media O(NlogN) y O(N²) en el peor de los casos.
Quick sort utiliza el principio de divide y vencerás, es decir que elegiremos un elemento de la tabla (que llamamos pivote), luego reorganizamos la tabla inicial en dos sub-tablas:
- Uno que contiene los elementos debajo del pivote.
- El otro que contiene los elementos por encima del pivote.
Continuamos con este proceso (que se llama partición, es decir, elegir un pivote y reorganizar la tabla) hasta que terminamos con una tabla dividida en N subtablas (N es el tamaño de la tabla), que está ordenada.
Tomemos 5, 9, 7, 3, 8 como una secuencia de números y ordenémosla en orden ascendente con el algoritmo de clasificación rápida:
5, 9, 7, 3, 8 -> elegimos el pivote, en nuestro caso elijo el elemento del medio, 7.
5, 3 | 7 | 9, 8 -> cortamos el cuadro en tres partes, una parte con los elementos debajo del pivote (5 y 3), la parte que contiene el pivote (7), y una parte con los elementos arriba del pivote (9 y 8) . Ya podemos decir que hemos colocado el pivote en su lugar definitivo en el cuadro, ya que los demás elementos son superiores o inferiores a él.
5, 3 | 7 | 9, 8 -> comenzamos de nuevo eligiendo un pivote nuevamente para cada subtabla creada.
3 | 5 | 7 | 8 | 9 -> último paso de la partición, ahora ningún subarreglo contiene más de un elemento, por lo que la clasificación ha terminado.
Ordenaciones recursivas: ordenación por fusión
Merge sort es uno de los algoritmos de clasificación más populares y eficientes. Y se basa en el paradigma Divide y vencerás.
Supongamos que tenemos que ordenar una matriz T. Un subproblema sería ordenar una subsección (sub-matriz) de esta matriz comenzando en el inicio del índice y terminando en el final del índice, denotado T[start..end].
Si el punto medio es el punto medio entre el inicio y el final, entonces podemos dividir el subarreglo T[inicio..fin] en dos arreglos T[inicio..medio] y T[medio + 1, fin]. En el paso Conquer, tratamos de clasificar las subredes T[start..middle] y T[middle + 1, end]. Si aún no hemos llegado al caso base (el subarreglo contiene solo un elemento), nuevamente dividimos estos dos subarreglos e intentamos ordenarlos.
Cuando la etapa de conquista alcanza la etapa base y obtenemos dos subarreglos ordenados T[start..mid] y T[mid + 1, end] para el arreglo T[start..mid], combinamos los resultados creando un matriz ordenada T[start..middle] de dos subarreglos ordenados T[start..middle] y T[middle + 1, end].
La función triMerge divide repetidamente la matriz en dos mitades (dos subarreglos) hasta que alcanzamos un punto en el que intentamos realizar triMerge en un subarreglo de tamaño 1, es decir, inicio == final.
Después de eso, la función de combinación se activa y combina las matrices ordenadas en una matriz más grande hasta que se fusiona toda la matriz. Después de eso, la función de combinación recupera los subconjuntos ordenados y los fusiona para clasificar gradualmente el conjunto completo.
La complejidad de tiempo de la ordenación por fusión es O(nLogn) en los 3 casos (peor, promedio y mejor) porque la ordenación por fusión siempre divide la matriz en dos mitades y toma un tiempo lineal para fusionar dos mitades.
Este pseudocódigo está muy simplificado:
- En la función triFusion, usamos la recursividad para dividir y luego fusionar nuestra matriz, y detenemos las llamadas recursivas cuando al subarreglo que estamos procesando solo le queda un elemento.
- La función merge es bastante explícita, nos permite crear a partir de dos subarreglos ordenados, un arreglo también ordenado en tiempo lineal.
