3º EP (Ordenações)

Reclamações

No horário da monitoria, até o final do curso. Lembre-se da máxima: pode ser pouco, mas é meu.

Critérios utilizados na correção

Não houve desconto para:

• variáveis static,
• classes esquisitas,
• gráficos com números jogados nos eixos e nenhuma outra explicação além do título.

Descontos:

• Nada de tabelas: -0,3; nada de gráficos: -0,3; imprecisão na cronometragem: -0,3. Se havia duas cronometragens e ao menos uma era precisa, não houve desconto.
• Para a análise, foram aceitos os argumentos mais maionésicos possíveis. Comentários do tipo "Sim, o BubbleSort é realmente muito lento" também foram considerados perfeitamente válidos.
• Mas dizer que "analisando o gráfico, podemos ver que o algoritmo é O(n log n)" não mereceu ponto nenhum.
• O novo algoritmo construído precisava ser bem justificado. Porém, para ganhar o ponto inteiro nesse item, era necessário ter ganho a pontuação inteira no novo algoritmo também (caso contrário, uma justificativa como "Não fiz porque não deu tempo" seria perfeitamente válida). Números que apareciam no algoritmo sem justificativas causaram uma perda de 0,2 aqui.
• Foram exigidos para o experimento:
• pelo menos 5 tamanhos diferentes de vetores (0,2);
• pelo menos 4 tipos de vetores: vetores ordenados (crescente e decrescentemente), aleatórios e parcialmente ordenados (0,1). Um vetor com 1, 2 ou 5 elementos fora de ordem (no meio de cinco mil) não foram considerados "parcialmente ordenados";
• para cada tipo e tamanho de vetor, a experiência deveria ser realizada mais de uma vez, e os dados deveriam constar no relatório (0,5). Aproveitando a ocasião, é bom lembrar que um vetor preenchido aleatoriamente não é a mesma coisa que um "vetor desordenado", como muitos chamaram.
• Ordenar o vetor já ordenado causou a perda de 0,9 no item "Qualidade experimental", indicando que a experiência (praticamente) estava sem validade.
• Surgiu uma bizarra variante do HeapSort que era O(n2). Isso causou uma perda de -0,8 no item "Implementação dos algoritmos". Alguém poderia informar de onde esse novo HeapSort surgiu?
• O novo algoritmo que levasse em conta apenas o tamanho ou o tipo de vetor ganhou um ponto (e a justificativa, meio). Ainda que o método para inferir o tipo do vetor fosse algo como "se dois elementos escolhidos ao acaso estão em ordem crescente, então...", não houve desconto. Porém, se o método para descobrir que um vetor estava ordenado era perguntar ao usuário, o algoritmo passou a valer só meio ponto.
  Para os que escreveram "Para vetores completamente ordenados, o BubbleSort é o melhor algoritmo de ordenação existente", gostaria de apresentar o algoritmo OVO, dos matemáticos russos Ovslov, Vladslav e Ornskov, em sua versão para Java:

/* ordena um vetor de inteiros; é importante que o vetor já esteja ordenado */

void OVO(int[] v) { }

O cálculo da complexidade desse algoritmo fica a cargo do leitor.