Resolução 3 - beecrowd 1258

Entrada

Casos com nome em uma linha e cor/tamanho na seguinte, até N = 0.

Saída

Cor crescente, tamanho decrescente e nome crescente.

Representação

Objetos Camiseta com três campos relacionados.

O comparador é uma cascata

Comparamos a cor. Somente quando ela empata consultamos o tamanho. Somente quando ambos empatam consultamos o nome. Um critério posterior nunca pode contrariar um critério anterior.

Por que a.tamanho > b.tamanho? Para os únicos valores possíveis, P > M > G na comparação de strings. Retornar -1 coloca P antes de M e M antes de G.

Mapa da solução

Modele cada camiseta

Nome, cor e tamanho viajam juntos durante todas as trocas.

Centralize os critérios em `comp`

O retorno negativo significa que a deve aparecer antes de b.

Particione pelo último objeto

i separa os itens menores que o pivô dos itens ainda não classificados.

Ordene os dois lados

As chamadas recursivas repetem a partição antes e depois da posição do pivô.

Execução interativa do Quicksort

Partições sobre objetos Camiseta

Velocidade

partição

Array de objetos

amarelo: pivô · vermelho: j · barra verde: i

Estado da partição

Intervalo
Pivô
Índice i

Critério que decide

1Corcrescente

2Tamanhodecrescente: P, M, G

3Nomecrescente

Objeto em j

Pivô atual

Ordem do array

Como ler `particao`

O intervalo segue a convenção [inicio, fim): inicio pertence ao intervalo e fim fica de fora. Por isso o pivô está em fim - 1.

i aponta para a primeira posição da região que ainda não contém um elemento menor que o pivô. Sempre que comp(V[j], pivo) < 0, o objeto de j é levado para essa região.

Código completo comentado

class Camiseta:
    # O objeto mantém juntos os dados da mesma inscrição.
    def __init__(self, nome, cor, tamanho):
        self.nome = nome
        self.cor = cor
        self.tamanho = tamanho


def comparar(a, b):
    # 1º critério: cor crescente.
    if a.cor != b.cor:
        return -1 if a.cor < b.cor else 1

    # 2º critério: tamanho decrescente.
    if a.tamanho != b.tamanho:
        return -1 if a.tamanho > b.tamanho else 1

    # 3º critério: nome crescente.
    if a.nome != b.nome:
        return -1 if a.nome < b.nome else 1
    return 0


def particionar(valores, inicio, fim):
    # fim é exclusivo; por isso o pivô está em fim - 1.
    pivo = valores[fim - 1]
    posicao_dos_menores = inicio

    for indice in range(inicio, fim - 1):
        if comparar(valores[indice], pivo) < 0:
            valores[posicao_dos_menores], valores[indice] = (
                valores[indice], valores[posicao_dos_menores]
            )
            posicao_dos_menores += 1

    # O pivô fica entre os menores e os maiores/iguais.
    valores[posicao_dos_menores], valores[fim - 1] = (
        valores[fim - 1], valores[posicao_dos_menores]
    )
    return posicao_dos_menores


def quicksort(valores, inicio, fim):
    if fim - inicio <= 1:
        return

    posicao_do_pivo = particionar(valores, inicio, fim)
    quicksort(valores, inicio, posicao_do_pivo)
    quicksort(valores, posicao_do_pivo + 1, fim)


primeiro_caso = True
while True:
    quantidade = int(input())
    if quantidade == 0:
        break

    if not primeiro_caso:
        print()  # O enunciado pede uma linha vazia entre casos.
    primeiro_caso = False

    camisetas = []
    for _ in range(quantidade):
        nome = input()
        cor, tamanho = input().split()
        camisetas.append(Camiseta(nome, cor, tamanho))

    quicksort(camisetas, 0, len(camisetas))

    for camiseta in camisetas:
        print(camiseta.cor, camiseta.tamanho, camiseta.nome)

Complexidade

O Quicksort costuma executar em O(n log n), mas pode chegar a O(n²) quando os pivôs geram partições muito desequilibradas. A pilha de recursão usa O(log n) no caso típico e O(n) no pior caso.