Solução Balé - Semana 3

0 Flares Facebook 0 0 Flares ×

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:

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:

Aqui, o código usando Insertion Sort:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: