> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# Algoritmos de ordenación: burbuja, selección, inserción, merge sort y quicksort

> Los algoritmos de ordenación explicados y animados: burbuja, selección, inserción, merge sort y quicksort, con su idea, código, complejidad en el mejor, medio y peor caso, estabilidad y memoria.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/ordenacion">
  Burbuja, selección, inserción, merge sort y quicksort animados, con contador de comparaciones.
</Card>

Ordenar una lista es uno de los problemas más estudiados de la informática. Hay decenas de algoritmos, y la diferencia entre uno sencillo y uno eficiente es enorme: con un millón de elementos, uno puede tardar horas y otro, menos de un segundo. Ver cada comparación e intercambio ayuda a entender **por qué**.

## Lo que vas a aprender

* La idea de cada algoritmo y cómo se programa.
* Contar comparaciones e intercambios.
* La complejidad en el mejor, el peor y el caso medio.
* Qué significa que un algoritmo sea estable o "in situ".
* Qué algoritmo elegir según los datos.

## Cómo se usa el simulador

* Elige el algoritmo: **burbuja**, **selección**, **inserción**, **merge sort** o **quicksort**.
* **Datos**: número de elementos (5 – 250) y su disposición inicial: **aleatorio**, **casi ordenado** o **invertido**. **🎲 Nuevos datos** genera otros.
* Avanza con **⏮**, **▶ Ordenar** y **⏭**, o arrastra el deslizador de pasos. Ajusta la **velocidad**.
* Los colores indican qué se **compara**, qué se **intercambia**, la **clave** y lo que ya está **ordenado**. Los contadores dan las comparaciones y los intercambios.
* **Cómo funciona** resume la idea y la complejidad de cada algoritmo.

## Fundamentos teóricos

### Burbuja

Recorre la lista comparando **vecinos** y los intercambia si están al revés. En cada pasada, el mayor "sube" hasta el final.

```c theme={null}
for (i = 0; i < n - 1; i++)
    for (j = 0; j < n - 1 - i; j++)
        if (v[j] > v[j + 1]) intercambia(&v[j], &v[j + 1]);
```

### Selección

Busca el **mínimo** de la parte sin ordenar y lo pone al principio. Hace siempre $n(n-1)/2$ comparaciones, pero solo $n - 1$ intercambios.

### Inserción

Toma cada elemento y lo **inserta** en su sitio dentro de la parte ya ordenada, desplazando los mayores. Como al ordenar las cartas de una mano. Con datos casi ordenados es muy rápido.

### Merge sort (mezcla)

**Divide** la lista en dos mitades, las ordena recursivamente y las **mezcla** en una sola ordenada. La mezcla de dos listas ordenadas es lineal.

$$
T(n) = 2\,T(n/2) + n \quad\Rightarrow\quad O(n\log n)
$$

### Quicksort (rápido)

Elige un **pivote**, coloca a su izquierda los menores y a su derecha los mayores (partición) y ordena recursivamente cada lado. Si el pivote parte la lista por la mitad, $O(n\log n)$; si siempre elige el mínimo o el máximo (por ejemplo, con datos ya ordenados y el primer elemento como pivote), degenera a $O(n^2)$.

### Comparativa

| Algoritmo | Mejor | Medio | Peor | Memoria extra | Estable |
| - | - | - | - | - | - |
| Burbuja | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Sí |
| Selección | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No |
| Inserción | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Sí |
| Merge sort | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | Sí |
| Quicksort | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | No |

Un algoritmo es **estable** si mantiene el orden relativo de los elementos iguales. Importa al ordenar por varios criterios (por ejemplo, por nota y luego por apellido).

## Ejemplos resueltos

<AccordionGroup>
  <Accordion title="Ejemplo 1 · Comparaciones de la burbuja" defaultOpen>
    Con 5 elementos en el peor caso: $4 + 3 + 2 + 1 = 10$, es decir, $n(n - 1)/2$.
  </Accordion>

  <Accordion title="Ejemplo 2 · n² frente a n log n">
    Con 1000 elementos: un algoritmo cuadrático hace unas $1000^2/2 = 500\,000$ comparaciones; merge sort, unas $1000 \cdot \log_2 1000 \approx 10\,000$. Cincuenta veces menos. Con un millón de elementos, la diferencia es de 25 000 veces.
  </Accordion>

  <Accordion title="Ejemplo 3 · Inserción con datos casi ordenados">
    Si cada elemento está como mucho a una posición de su sitio, inserción hace menos de $2n$ comparaciones: prácticamente lineal.
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="Casi ordenado">
    Con datos casi ordenados, compara inserción y selección. ¿Cuál hace menos comparaciones?
  </Step>

  <Step title="El peor caso de quicksort">
    Con datos invertidos, mira cómo trabaja quicksort. ¿Se acerca a $n^2$?
  </Step>

  <Step title="Muchos datos">
    Sube a 250 elementos y compara los contadores de burbuja y merge sort.
  </Step>
</Steps>

## Errores frecuentes

* **Pensar que el algoritmo más rápido siempre es el mismo.** Depende del tamaño y de cómo estén los datos.
* **Olvidar el caso peor de quicksort.**
* **Confundir intercambios con comparaciones** al medir el coste.

## Herramientas relacionadas

<CardGroup cols={3}>
  <Card title="Mejor y peor caso" icon="stopwatch" href="/programacion/c/mejor-peor-caso">
    Medir el coste experimentalmente.
  </Card>

  <Card title="Divide y vencerás" icon="code-branch" href="/programacion/c/divide-y-venceras">
    La idea de merge sort y quicksort.
  </Card>

  <Card title="Recursión" icon="arrows-rotate" href="/programacion/c/recursion">
    Funciones que se llaman a sí mismas.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.