Em Produção · ICPC · Fundamentos
Quantas trocas até ficar ordenado?
Contar inversões é um problema famoso com muitas soluções conhecidas. O Bubblesort conta trocando; o Mergesort conta sem olhar cada par.
Pegue [1,4,3,2] e rode uma passada de Bubblesort. Compare 1 e 4: deixa. Compare 4 e 3: troca. Compare 4 e 2: troca. Sobra [1,3,2,4], e mais uma troca termina o serviço. Três trocas no total.
Não é coincidência. Cada troca de vizinhos desfaz exatamente uma inversão, um par fora de ordem, então o número de trocas do Bubblesort é o número de inversões. Um contador ao lado da troca é o algoritmo inteiro.
Também é O(n²), o que serve para quatro números e não serve para um milhão. O Mergesort ordena em O(n log n) e consegue contar enquanto ordena. Quando o merge pega um elemento da metade direita antes do que sobrou da metade esquerda, esse elemento pula todos eles, e cada pulo é uma inversão. Some tudo e você nunca olha um par diretamente.
Carregando a figura interativa…
Versão estática: [1,4,3,2] tem 3 inversões; a primeira passada do Bubblesort termina em [1,3,2,4].
A contagem é mais do que truque de maratona. É uma distância entre duas ordenações, o número de pares em que duas listas discordam. Quando um reranker novo vai para produção e você quer saber o quanto ele se afastou do ranking antigo, o número é esse, e agora dá para calcular em O(n log n).