Pular para o conteúdo

O básico de ordenação

Aula 1 de 10 · 4 min

O básico de ordenação

Passo 1 de 5

Cinco registros, na ordem em que chegaram. Avalie qualquer ordenação por três coisas: tempo, memória extra e estabilidade.

A ideia

Toda ordenação por comparação funciona comparando pares e reorganizando-os. Avalie cada uma por três critérios: tempo, memória extra e estabilidade. Uma ordenação estável mantém itens iguais na ordem em que chegaram.

Exemplo do mundo real

Ordene uma planilha por nome e depois ordene de novo por cidade. Com uma ordenação estável, os nomes dentro de cada cidade continuam em ordem alfabética; com uma instável, aquele trabalho anterior se embaralha. É a estabilidade que torna possível ordenar em camadas.

O código

Sua vez

O que isto imprime?

pairs = [("x", 2), ("y", 1), ("z", 2)]
out = sorted(pairs, key=lambda p: p[1])
print([p[0] for p in out])

Mini quiz

1 / 3

Uma ordenação estável garante que: