MO640 - Exercícios - Sobre a aula de 2006-05-31

1. Ordene por transposições de prefixo a seguinte permutação: 9 8 7 6 5 4 3 2 1.
   
   A melhor ordenação sugerida em aula foi a seguinte:
   
   •9•8•7•6•5•4•3•2•1• (ρ(1,5,8))
   
   •5•4•3•9•8•7•6•2•1• (ρ(1,3,6))
   
   •3•9•8•5•4•7•6•2•1• (ρ(1,3,9))
   
   •8•5•4•7•6•2 3•9•1• (ρ(1,3,5))
   
   •4•7 8•5 6•2 3•9•1• (ρ(1,4,8))
   
   •5 6•2 3 4•7 8 9•1• (ρ(1,3,6))
   
   •2 3 4 5 6 7 8 9•1• (ρ(1,9,10))
   
   •1 2 3 4 5 6 7 8 9
   
   Podemos perceber que a permutação foi ordenada com sete transposições de prefixo, que é exatamente o valor de n - n/4 (arredondando n/4 para baixo), estando, portanto, dentro dos limites definidos no artigo de Dias e Meidanis de 2002 (ela foi gerada justamente com o algoritmo ali apresentado para ordenar permutações reversas).

MO640 Home