domingo, 11 de março de 2018

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.

Nenhum comentário:

Postar um comentário