Hypnotic Patterns
PT
Algoritmos · Corrida de ordenação

Por que razão nenhuma ordenação bate n log n

A regra

Algoritmos diferentes ordenam os mesmos dados, misturados ao acaso. Cada um põe ordem no caos à sua maneira.

É reproduzido a partir do YouTube depois de um clique.

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

Por que razão funciona

Misture um baralho de cartas e ordene-o comparando duas cartas de cada vez. Alguns métodos comparam cartas vizinhas vezes sem conta; outros dividem o baralho em metades, depois em metades das metades. Com a mesma mistura, os segundos acabam muito mais cedo, e nenhum método que só compara consegue fazer muito melhor do que isso.

comparações ≥ log₂(n!) ≈ n·log₂ n − 1,44·nbubble sort: até n·(n − 1) ÷ 2

Construa-o em Python

Python 3 · numpy · matplotlib

Quatro ordenações na mesma lista misturada ao acaso, com a contagem das suas comparações.

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

Experimente: Defina n = 1000: a contagem do bubble sort cresce cerca de cem vezes, a do merge sort cerca de 16 vezes.

Aprenda este script linha a linha, com exercícios e um quiz → · execute-o no Google Colab (em inglês) →

Shorts

Fontes