Ordenación por selección y burbuja

¿Qué es la ordenación por selección?

Es un algoritmo de ordenación que divide la lista en dos partes: ordenada y no ordenada, seleccionando el elemento más pequeño de la parte no ordenada.

Pasos del algoritmo de ordenación por selección:

- Buscar el mínimo - Intercambiar con el primer elemento de la parte no ordenada - Repetir hasta que esté ordenada

¿Es estable la ordenación por selección?

No, ya que puede cambiar el orden relativo de elementos iguales durante el proceso de intercambio.

Complejidad temporal del algoritmo:

La complejidad en el peor y caso promedio es $\displaystyle O(n^2)$, siendo $\displaystyle n$ el número de elementos a ordenar.

¿Qué se hace en cada iteración?

Se busca el elemento mínimo en la parte no ordenada y se intercambia con el primer elemento de esa parte.

Ventajas de la ordenación por selección:

- Simplicidad - No requiere memoria adicional - Mejora el rendimiento en listas pequeñas

Ejemplo: Ordenar [64, 25, 12, 22, 11]

1. Mínimo: 11, Intercambiar con 64 2. Mínimo: 12, Intercambiar con 25 3. Mínimo: 22, Intercambiar con 25 Resultado: [11, 12, 22, 25, 64]

¿Qué tipo de algoritmo es la ordenación por selección?

Es un algoritmo in situ, ya que no requiere almacenamiento adicional más allá de los elementos a ordenar.

Comparación de selección y burbuja:

La selección tiene $\displaystyle O(n^2)$ en todos los casos, mientras que la burbuja puede ser $\displaystyle O(n)$ en el mejor caso.

¿La ordenación por selección es eficiente?

No es eficiente para listas grandes debido a su complejidad cuadrática. Se prefiere para listas pequeñas.

¿Cuántas pasadas realiza en un array de n elementos?

Realiza $\displaystyle n - 1$ pasadas, ya que en cada pasada se coloca un elemento en su posición correcta.

¿Qué se intercambia en la selección?

Se intercambia el elemento mínimo encontrado con el primer elemento de la parte no ordenada.

¿La ordenación por selección modifica la lista original?

Sí, la lista original se modifica durante el proceso de ordenación, resultando en una lista ordenada.

Desventajas de la ordenación por selección:

- Rendimiento lento en listas grandes - No estable - Múltiples intercambios innecesarios

¿Cuántas comparaciones se realizan en total?

Se realizan $\displaystyle \frac{n(n-1)}{2}$ comparaciones en el peor caso para un array de tamaño n.

¿Qué tipo de datos maneja el algoritmo?

Puede manejar cualquier tipo de datos que se puedan comparar, como números y cadenas.

¿Qué es la ordenación por burbuja?

Un algoritmo de ordenación que compara elementos adyacentes y los intercambia si están en el orden incorrecto.

Características clave de la burbuja

- Simple de implementar - Ineficiente para grandes listas - Complejidad temporal: $\displaystyle O(n^2)$

Paso inicial del algoritmo

Recorrer el array desde el inicio hasta el penúltimo elemento.

Complejidad espacial de burbuja

Es $\displaystyle O(1)$, ya que utiliza solo un espacio adicional constante.

¿Es estable la ordenación por burbuja?

Sí, mantiene el orden relativo de los elementos iguales.

¿Qué ocurre en una iteración?

Se comparan pares de elementos y se intercambian si están en el orden incorrecto.

Ejemplo: ordenar [5, 3, 8]

[5, 3, 8] → [3, 5, 8] tras intercambiar 5 y 3.

¿Cuándo se detiene el algoritmo?

Cuando se completa un recorrido sin realizar intercambios.

¿Qué mejora se puede aplicar?

Incluir una bandera para detectar si ya está ordenado, optimizando el proceso.

¿Qué hace el algoritmo en cada pase?

- Mueve el elemento más grande al final - Reduce el rango de la próxima iteración.

Comparación: burbuja y selección

Burbuja: intercambia adyacentes. Selección: busca el mínimo.

¿Cuál es la desventaja principal?

Es muy lento para listas grandes comparado con otros algoritmos de ordenación.

¿Cuál es la principal diferencia entre ambos algoritmos?

La ordenación por selección elige el mínimo de la lista y lo coloca al principio, mientras que la burbuja compara elementos adyacentes y los intercambia si están en el orden incorrecto.

Ventajas de la ordenación por burbuja

- Fácil de implementar - Bueno para listas pequeñas - Visualmente intuitivo

Verdadero o falso: La ordenación por selección es más eficiente que la burbuja.

Falso. Ambos algoritmos tienen una complejidad de $\displaystyle O(n^2)$ en el peor de los casos, pero la selección puede ser más eficiente en algunos casos prácticos.

Comparación de complejidad temporal: Burbuja vs Selección

Ambos tienen: - Mejor caso: $\displaystyle O(n)$ (burbuja, si está casi ordenado) - Peor caso: $\displaystyle O(n^2)$ - Complejidad promedio: $\displaystyle O(n^2)$

Fill in the blank: Ambos algoritmos son tipos de ________.

Ordenación no eficiente.

Ejemplo de ordenación por selección

Lista: [5, 3, 8, 4] 1. Mínimo = 3, intercambiar con 5. 2. Nueva lista = [3, 5, 8, 4] 3. Continuar hasta completar la lista.

Causa → Efecto: Dificultad de la burbuja

Causa: Compara elementos adyacentes. Efecto: Tarda más en listas largas debido a múltiples pasadas.

¿Qué algoritmo es mejor para listas pequeñas?

La ordenación por burbuja es generalmente más adecuada para listas pequeñas debido a su simplicidad y menor sobrecarga.