Solução Balé – Semana 3

Solução por Lucca Siaudzionis

Este problema é um problema clássico: contar o número de inversões para ordenar um array. Há várias formas de resolver este problema, algumas são:

• Insertion Sort
• Merge Sort
• BIT – Binary Indexed Tree (Árvore Indexada Binária), também conhecida como Fenwick Tree (Árvore de Fenwick)

Recomendamos o estudo dos três algoritmos, principalmente dos dois últimos. O mais poderoso dos três é o BIT, e um material muito bom de estudo dele (em inglês) pode ser visto aqui.

Com o BIT, resolvemos o problema contando, para cada número, quantos números maiores que ele aparecem antes dele no array e somando todos esses resultados. Para isso, toda vez que lermos um valor $$x$$, fazemos a operação $$insere(x)$$, e a quantidade de números maiores que $$x$$ que apareceram antes dele será $$somaate(\infty) – somaate(x)$$ (note que essas somas devem ser calculadas assim que é feita $$insere(x)$$, pois estes resultados vão mudar depois).

Aqui, o código usando BIT:

https://gist.github.com/luccasiau/23016d5534d7b788163a

Aqui, o código usando Insertion Sort:

https://gist.github.com/luccasiau/defdb36ecad62784d04f