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.

Algoritmos com Java: Busca Binária

Na série "Algoritmos com Java" iremos compartilhar alguns algoritmos que implementamos com Java. Segue abaixo uma implementação de Busca Binária. Notem que há bastante uso de Java 8 na parte que tratamos a entrada do usuário.

Aqui está um exemplo de uso:

Para rodar copiem o código acima em um arquivo chamado BuscaBinaria.java, compilem com Java 8 usando javac e executem usando java passando a lista de números separados por vírgula e o que deve ser buscado separado por um espaço.
Notem que essa é uma possível implementação, há outras formas que não iremos discutir nem comparar. Os tópicos de algoritmos ficarão aqui sempre tentando apimentar um pouco o algoritmo principal com Java 8 e 9, mas a implementação principal ficará sempre em um método separado, assim separamos a API da linguagem do algoritmo.
Em breve teremos mais algoritmos com Java!