Hypnotic Patterns
DE
Algorithmen · Sortierwettlauf

Warum kein Sortierverfahren n log n schlagen kann

Die Regel

Verschiedene Algorithmen sortieren dieselben gemischten Daten. Jeder bringt das Chaos auf seine eigene Weise in Ordnung.

Läuft nach einem Klick von YouTube.

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

Warum es funktioniert

Misch ein Kartenspiel und sortiere es, indem du immer zwei Karten vergleichst. Manche Verfahren vergleichen immer wieder Nachbarn; andere teilen das Spiel in Hälften, dann in Hälften der Hälften. Bei derselben Mischung ist die zweite Art viel früher fertig, und kein Verfahren, das nur vergleicht, kann es viel besser.

Vergleiche ≥ log₂(n!) ≈ n·log₂ n − 1,44·nBubblesort: bis zu n·(n − 1) ÷ 2

Bau es selbst

Python 3 · numpy · matplotlib

Vier Sortierverfahren auf derselben gemischten Liste, mit gezählten Vergleichen.

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

Probier: Setze n = 1000: Die Zahl bei Bubblesort wächst etwa auf das Hundertfache, bei Mergesort etwa auf das Sechzehnfache.

Lerne dieses Skript Zeile für Zeile, mit Übungen und einem Quiz → · starte es in Google Colab (auf Englisch) →

Shorts

Quellen