Hypnotic Patterns
FR
Algorithmes · Course de tris

Pourquoi aucun tri ne peut battre n log n

La règle

Différents algorithmes trient les mêmes données mélangées. Chacun met de l’ordre dans le chaos à sa manière.

Lecture depuis YouTube après un clic.

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

Pourquoi ça marche

Mélange un jeu de cartes et trie-le en comparant deux cartes à la fois. Certaines méthodes comparent des voisines encore et encore ; d’autres coupent le jeu en deux, puis chaque moitié en deux. Sur le même mélange, les secondes finissent bien plus tôt, et aucune méthode qui ne fait que comparer ne peut faire beaucoup mieux.

comparaisons ≥ log₂(n!) ≈ n·log₂ n − 1,44·ntri à bulles : jusqu’à n·(n − 1) ÷ 2

Construis-le toi-même

Python 3 · numpy · matplotlib

Quatre tris sur la même liste mélangée, avec le compte de leurs comparaisons.

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))

Essaie : Mets n = 1000 : le compte du tri à bulles est multiplié par cent environ, celui du tri fusion par seize environ.

Apprends ce script ligne par ligne, avec des exercices et un quiz → · lance-le dans Google Colab (en anglais) →

Shorts

Sources