Ordenamiento estable y el ordenamiento incorporado en Python

Problema

Las fechas que se desordenan

En el panel de administración de la tienda los pedidos están por fecha: el más antiguo arriba. Una empleada hace clic en el encabezado «Cliente» para ver juntos los pedidos de cada cliente. Espera que los pedidos de Lucía estén uno debajo del otro, y todavía por fecha.

Esto es lo que da un ordenamiento por cliente con el ordenamiento por selección:

from dataclasses import dataclass


@dataclass
class Order:
    date: str
    customer: str
    amount: float

def selection_sort(orders):
    for i in range(len(orders) - 1):
        smallest = i
        for j in range(i + 1, len(orders)):
            if orders[j].customer < orders[smallest].customer:
                smallest = j
        orders[i], orders[smallest] = orders[smallest], orders[i]

orders = [
    Order("2026-10-03", "Lucía", 42.50),
    Order("2026-10-05", "María", 18.00),
    Order("2026-10-07", "Lucía", 120.00),
    Order("2026-10-09", "Pedro", 64.90),
    Order("2026-10-12", "María", 35.20),
    Order("2026-10-15", "Lucía", 9.99),
]
selection_sort(orders)
for o in orders:
    print(o.customer, o.date)

Lucía 2026-10-03
Lucía 2026-10-07
Lucía 2026-10-15
María 2026-10-12
María 2026-10-05
Pedro 2026-10-09

Los clientes están ordenados. Pero con María el pedido del 12 de octubre va antes que el del 5 de octubre. La empleada ve el último pedido de María como el primero y la llama por el equivocado.

La idea

Estabilidad: las claves iguales conservan su orden

Un ordenamiento es estable si los elementos con la misma clave se quedan en el orden en que estaban. Los dos pedidos de María tienen la misma clave (el cliente). Un ordenamiento estable los deja como llegaron: primero el 5 de octubre, luego el 12.

Cuáles son estables:

ordenamiento por inserción: mueve un elemento solo más allá de los estrictamente mayores, así que nunca salta sobre uno igual;
ordenamiento por mezcla: en un empate toma de la mitad izquierda (ordenamiento por mezcla);
ordenamiento por conteo: coloca de izquierda a derecha (ordenamiento por conteo).

Cuáles no:

el ordenamiento por selección, quicksort y el ordenamiento por montículo. Los tres intercambian elementos a distancia. El intercambio lleva un elemento por encima de todo lo que hay entre los dos lugares, y los iguales de en medio quedan detrás de él.

La estabilidad solo importa cuando el elemento lleva más que la clave. Dos números 5 iguales no se pueden distinguir. Dos pedidos de María sí.

Míralo

Ordenamiento por selección contra ordenamiento por inserción

La misma lista con ordenamiento por inserción:

def insertion_sort(orders):
    for i in range(1, len(orders)):
        current = orders[i]
        j = i - 1
        while j >= 0 and current.customer < orders[j].customer:
            orders[j + 1] = orders[j]
            j -= 1
        orders[j + 1] = current

orders = [
    Order("2026-10-03", "Lucía", 42.50),
    Order("2026-10-05", "María", 18.00),
    Order("2026-10-07", "Lucía", 120.00),
    Order("2026-10-09", "Pedro", 64.90),
    Order("2026-10-12", "María", 35.20),
    Order("2026-10-15", "Lucía", 9.99),
]
insertion_sort(orders)
for o in orders:
    print(o.customer, o.date)

Lucía 2026-10-03
Lucía 2026-10-07
Lucía 2026-10-15
María 2026-10-05
María 2026-10-12
Pedro 2026-10-09

def selection_sort(orders):
    for i in range(len(orders) - 1):
        smallest = i
        for j in range(i + 1, len(orders)):
            if orders[j].customer < orders[smallest].customer:
                smallest = j
        orders[i], orders[smallest] = orders[smallest], orders[i]

def insertion_sort(orders):
    for i in range(1, len(orders)):
        current = orders[i]
        j = i - 1
        while j >= 0 and current.customer < orders[j].customer:
            orders[j + 1] = orders[j]
            j -= 1
        orders[j + 1] = current

Paso a paso, en palabras

Seis pedidos, ordenados por fecha. Ahora por cliente, con ordenamiento por selección.
Lugar 0: el cliente menor de aquí en adelante es Lucía 03/10, ya está en su lugar.
Lugar 1: Lucía 07/10 se intercambia con María 05/10.
Lugar 2: Lucía 15/10 se intercambia con María 05/10. El intercambio lejano manda María 05/10 al final, detrás de María 12/10.
Dos intercambios más: María va antes que Pedro.
Ordenado por cliente, pero María 12/10 va antes que María 05/10. El ordenamiento por selección no es estable: las claves iguales pueden perder su orden.
La misma lista con ordenamiento por inserción. Un pedido se mueve solo más allá de los estrictamente mayores, así que María 05/10 se queda antes que María 12/10. Estable.

El pedido que el ordenamiento por inserción mueve a la izquierda se detiene delante del primero que no es mayor. Sobre uno igual no se salta, y las fechas de María se quedan 05, luego 12.

Pruébalo

Encuentra el error

Alguien cambió una comparación en el ordenamiento por inserción. El ordenamiento sigue siendo por cliente, pero las fechas dentro de cada cliente salen al revés:

def insertion_sort(orders):
    for i in range(1, len(orders)):
        current = orders[i]
        j = i - 1
        while j >= 0 and current.customer <= orders[j].customer:
            orders[j + 1] = orders[j]
            j -= 1
        orders[j + 1] = current

orders = [
    Order("2026-10-03", "Lucía", 42.50),
    Order("2026-10-05", "María", 18.00),
    Order("2026-10-07", "Lucía", 120.00),
    Order("2026-10-09", "Pedro", 64.90),
    Order("2026-10-12", "María", 35.20),
    Order("2026-10-15", "Lucía", 9.99),
]
insertion_sort(orders)
for o in orders:
    print(o.customer, o.date)

Lucía 2026-10-15
Lucía 2026-10-07
Lucía 2026-10-03
María 2026-10-12
María 2026-10-05
Pedro 2026-10-09

¿En qué línea está el error?

Elige la línea con el error.

<= deja que el actual también se ponga delante de los iguales. Los pedidos de un cliente salen en orden inverso. Vuelve a poner el < estricto.

Míralo

El ordenamiento incorporado

En la práctica no escribes tu propio ordenamiento, usas el incorporado. Veinte pedidos, por fecha, ordenados por cliente. Se imprimen las fechas de cada cliente:

En Python list.sort y sorted son estables: la documentación lo promete de forma explícita.

orders.sort(key=lambda o: o.customer)
show(orders)

Lucía: 01 04 06 09 12 15 18
María: 02 05 08 11 13 16 19
Pedro: 03 07 10 14 17 20

Las fechas de cada cliente están en orden: 01, 04, 06…

La idea

Qué usa el ordenamiento incorporado de cada lenguaje

Java. Arrays.sort para un arreglo de primitivos (int[], double[]) es quicksort de doble pivote: no es estable, pero con números eso no importa. Para objetos (Arrays.sort(Object[]), List.sort, Collections.sort) es TimSort: estable.
C#. Array.Sort y List<T>.Sort son introsort: un quicksort que cambia a ordenamiento por montículo cuando la partición se hace demasiado profunda y a ordenamiento por inserción para partes pequeñas. No es estable. LINQ OrderBy y ThenBy son estables.
Python. list.sort y sorted son TimSort: estable.
JavaScript. Array.prototype.sort tiene que ser estable desde ES2019. V8 (Chrome, Node.js) usa TimSort desde la versión 7.0.

TimSort es un ordenamiento por mezcla que busca trozos ya ordenados en la entrada y los mezcla. Los datos reales suelen estar casi ordenados, y entonces está cerca de O(n).

Más precisamente, para curiosos

Python: desde la versión 3.11 la regla con la que TimSort elige qué trozos mezclar es powersort (de Munro y Wild). El ordenamiento sigue siendo estable, las mezclas están mejor ordenadas.
Java: la estabilidad de verdad no importa con primitivos, porque dos int iguales no se pueden distinguir. Por eso allí se eligió el quicksort más rápido.
C#: introsort mantiene O(n log n) en el peor caso gracias al ordenamiento por montículo (ordenamiento por montículo). El precio es la estabilidad.
JavaScript: antes de ES2019 V8 usaba quicksort para arreglos largos y el ordenamiento no era estable. El código escrito entonces a veces tiene «arreglos» para eso que hoy no hacen falta.
En los cuatro: la comparación tiene que ser consistente. Si dice que A va antes que B y que B va antes que A, el resultado es impredecible, y en Java List.sort puede lanzar IllegalArgumentException: Comparison method violates its general contract!.

Míralo

Ordenar por varias claves

A menudo la clave es más de un campo: por cliente, y dentro de cada cliente primero el importe mayor.

key devuelve una tupla: las tuplas se comparan campo a campo, como las palabras en un diccionario. -o.amount invierte el importe, para que el mayor vaya primero.

orders.sort(key=lambda o: (o.customer, -o.amount))

Lucía 2026-10-07 120.00 €
Lucía 2026-10-03 42.50 €
Lucía 2026-10-15 9.99 €
María 2026-10-12 35.20 €
María 2026-10-05 18.00 €
Pedro 2026-10-09 64.90 €

Hay una segunda forma, que solo funciona con un ordenamiento estable: ordena primero por la segunda clave, luego por la primera. El segundo ordenamiento conserva el orden de las claves iguales, y ese orden ya es por la segunda clave. El último ordenamiento es el principal.

Más precisamente, para curiosos

Cuándo es útil la segunda forma: cuando las claves no caben en una comparación. Por ejemplo, en Python -o.amount no sirve para texto: para «por cliente, y dentro de cada uno por nombre de producto en orden inverso» ordenas dos veces, primero key=lambda o: o.product, reverse=True, luego key=lambda o: o.customer.

Pruébalo

Predice la salida

Dos ordenamientos estables uno tras otro: primero por importe, el mayor primero, luego por cliente. ¿Qué imprime el programa?

orders = [
    Order("2026-10-05", "María", 35.20),
    Order("2026-10-06", "Lucía", 9.99),
    Order("2026-10-07", "María", 18.00),
    Order("2026-10-08", "Lucía", 42.50),
]
orders.sort(key=lambda o: o.amount, reverse=True)
orders.sort(key=lambda o: o.customer)
for o in orders:
    print(o.customer, f"{o.amount:.2f}")

Respuesta

Lucía 9.99 / Lucía 42.50 / María 18.00 / María 35.20

Lucía 42.50 / Lucía 9.99 / María 35.20 / María 18.00

Lucía 42.50 / María 35.20 / María 18.00 / Lucía 9.99

Ejercicio

Entregas por ciudad

Resuelve la tarea en tu editor.

Por ciudad, luego por importe. Seis entregas tienen una ciudad y un importe. Ordénalas por ciudad, y dentro de una ciudad el importe mayor primero, con el ordenamiento incorporado de tu lenguaje.

Plovdiv 24.00 €
Plovdiv 15.30 €
Sofía 80.00 €
Sofía 12.50 €
Varna 40.00 €
Varna 9.90 €

Más tareas

Dos veces. Haz lo mismo con dos ordenamientos estables, sin meter dos claves en una comparación. ¿Qué ordenamiento va primero?
Inestable a mano. Ordena las entregas por ciudad con el ordenamiento por montículo de la lección sobre montículos. ¿Los importes dentro de una ciudad se quedan en el orden en que estaban?
Un ordenamiento por selección estable. ¿Puede el ordenamiento por selección ser estable si, en lugar de intercambiar, lleva el menor a su lugar y empuja el resto hacia la derecha? ¿Qué cuesta eso?

Test

Ponte a prueba

1. ¿Qué significa que un ordenamiento sea estable?Los elementos con la misma clave se quedan en el orden en que estaban antesNo necesita memoria extraSiempre es O(n log n)

2. ¿Cuáles de estos son estables, tal como se suelen escribir?Quicksort y ordenamiento por selecciónOrdenamiento por inserción y por mezclaOrdenamiento por selección y por montículo

3. La lista está ordenada por fecha. La quieres por cliente, y dentro de cada cliente por fecha. ¿Qué basta?Un ordenamiento por cliente con cualquier algoritmoUn ordenamiento estable por clienteNo basta nada, hace falta un ordenamiento por dos claves

4. En C# necesitas un ordenamiento estable de pedidos por cliente. ¿Qué usas?List.SortOrderBy de LINQArray.Sort con un Comparison

Ordenamiento estable y el ordenamiento incorporado

Cookies