Hypnotic Patterns
ES
Algoritmos · Carrera de ordenamiento

Por qué ningún algoritmo de ordenamiento puede superar n log n

La regla

Distintos algoritmos ordenan los mismos datos desordenados. Cada uno pone orden en el caos a su manera.

Se reproduce desde YouTube tras hacer clic.

Eight Ways to Put Chaos in Order 30 Minutes of Hypnotic Sorting

Por qué funciona

Baraja un mazo de cartas y ordénalo comparando dos cartas cada vez. Algunos métodos comparan vecinas una y otra vez; otros dividen el mazo en mitades, y luego en mitades de mitades. Con la misma mezcla, el segundo tipo termina mucho antes, y ningún método que solo compare puede hacerlo mucho mejor.

comparaciones ≥ log₂(n!) ≈ n·log₂ n − 1,44·nburbuja: hasta n·(n − 1) ÷ 2

Constrúyelo tú

Python 3 · numpy · matplotlib

Cuatro ordenamientos sobre la misma lista desordenada, contando sus comparaciones.

sorting-race.py 
"""Sorting race: four algorithms on the same shuffled list, counting their comparisons.
Run: python sorting-race.py   (needs: pip install numpy matplotlib)
"""
import math

import numpy as np
import matplotlib.pyplot as plt

plt.style.use("dark_background")

n = 100
data = list(np.random.default_rng().permutation(n))
count = {"comparisons": 0}


def less(a, b):  # every algorithm compares only through this, so we can count
    count["comparisons"] += 1
    return a < b


def bubble(xs):
    xs = xs[:]
    for end in range(len(xs) - 1, 0, -1):
        for i in range(end):
            if less(xs[i + 1], xs[i]):
                xs[i], xs[i + 1] = xs[i + 1], xs[i]
    return xs


def insertion(xs):
    xs = xs[:]
    for i in range(1, len(xs)):
        j = i
        while j > 0 and less(xs[j], xs[j - 1]):
            xs[j], xs[j - 1] = xs[j - 1], xs[j]
            j -= 1
    return xs


def merge(xs):
    if len(xs) < 2:
        return xs
    left, right = merge(xs[: len(xs) // 2]), merge(xs[len(xs) // 2 :])
    out = []
    while left and right:
        out.append(left.pop(0) if not less(right[0], left[0]) else right.pop(0))
    return out + left + right


def quick(xs):
    if len(xs) < 2:
        return xs
    pivot, rest = xs[0], xs[1:]
    smaller = [x for x in rest if less(x, pivot)]
    return quick(smaller) + [pivot] + quick([x for x in rest if x not in smaller])


results = {}
for name, sort in [("bubble", bubble), ("insertion", insertion), ("merge", merge), ("quick", quick)]:
    count["comparisons"] = 0
    assert sort(data) == sorted(data)
    results[name] = count["comparisons"]
print(results, "| at least log2(n!) =", math.ceil(math.log2(math.factorial(n))))

plt.figure(figsize=(7, 4))
plt.bar(list(results), list(results.values()), color=["#f0abfc", "#c4b5fd", "#5eead4", "#5eead4"])
plt.axhline(math.log2(math.factorial(n)), color="white", linestyle="--", label="log2(n!): no comparison sort does better")
plt.ylabel(f"comparisons for n = {n}")
plt.legend()
plt.show()

# Try: n = 1000 (bubble sort needs about n*n/2, merge sort about n*log2(n))

Prueba: Pon n = 1000: la cuenta de burbuja crece unas cien veces; la de mezcla, unas dieciséis.

Aprende este script línea a línea, con ejercicios y un cuestionario → · ejecútalo en Google Colab (en inglés) →

Shorts

Fuentes