Algoritmos com Java: BubbleSort e geração de caso de testes para o URI 1388

Os algoritmos de ordenação mais lentos são bem conhecidos: selection sort, bubble sort entre outros. Nessa postagem vamos compartilhar uma implementação do BubbleSorte e, de quebra, um gerador de caso de testes para o problema 1388 do URI.

Que vergonha ainda não resolvi 100%!

Para quem não conhece, o URI Online Judge é uma plataforma espetacular cheia de algoritmos para encontrar uma solução e enviar para avaliação no servidor deles.

O problema 1388 do URI é de nível 6, um dos mais altos! E ele é sobre fazer uma engenharia reversa no Bubble Sort. Há dois problemas com esse problema (hehe):

1. Os casos de teste são escassos, são só três! Você nunca cobre todos os casos de entrada com 3 casos de teste...
2. A forma mais óbvia de resolver, que é desordenar um vetor fazendo o bubble sorte ao contrário até que ele pegue uma ordem que satisfaça a entrada, é custosa e dá erro de Time Limit Exceed. 

Logo você precisa de uma forma que resolva pegando atalhos, de preferência elegantes, sem gambiarras. Por isso é legal que você teste bem, pois o URI só vai falar que você não cobriu todos os casos de teste, se houve erro de runtime, se excedeu o tempo e por aí vai. Nesse exato momento criei o pequeno código abaixo que está me auxiliando. É java 8 puro. Para compilar: javac GeraCasoTeste1388.java e rodar: java GeraCasoTeste1388

Será que tá gerando caso de teste certos?

Você pode até passar o tamanho do array que você quer ver gerado Só um pequeno adendo. Faça sempre testes de mesa, pois pode haver mais de uma sequência que satisfaz a condição. Leia com atenção o URI que você vai entender!. Enfim,segue o código.