Arquivo Discussoes de Programacao e Tecnologia Estava lendo um exercicio em um livro de Java e gostaria de saber se é verdade ou mentira que para ordenar 6 números é possível fazer isso com menos que 8 comparações isso é verdade?
Eu acho q é verdade pq no melhor caso pode ser 6log6 que é 4,7 se eu não me engano,esse raciocinio que eu fiz está correto ou não???
PS:Nesse caso eu utilizei base 10 para o log tem q ser base 10 ou base 2???
Pois é cara, os “melhores” algoritmos de ordenação baseados em comparação têm complexidade O(nlogn). Isso quer dizer que no pior caso, levarão esse tempo para ordenar uma sequencia de n elementos. Dentre esses, posso citar o mergeSort e o HeapSort.
Faz o seguinte, implementa um desses qualquer, em java ou em c mesmo, e conta quantas comparações eles fazem.Você consegue o código completo na net, mas eu sugiro que vc pesquise sobre o conceito de cada um e implemente você mesmo! 
Outra coisa, o log nesse caso está em base 2. Para facilitar, foi padrozinado que quando aparecer log e o mesmo não tiver base, a base padrão é 2, isso no contexto de computação.
A entendi cara só estava com dúvida mesmo sobre a questão da base do log pq é um exercicio q o meu professor falou q talvez cobre um parecido na prova que pergunta se é possível ordenar 6 numeros com 8 comparações ´só q se for em base 2 isso não é possivel pq se multiplicar 6 por log6 na base 2 da mais que 12 então ja resolve meu problema
vlw ai obrigado
Tem também o Quicksort que, dependendo de como o pivô for escolhido pode ter uma complexidade maior.
Seria interessante você pegar 6 números, implementar o Quicksort e ver isso, variando a posição do pivô.
Tem também o Quicksort que, dependendo de como o pivô for escolhido pode ter uma complexidade maior.
Seria interessante você pegar 6 números, implementar o Quicksort e ver isso, variando a posição do pivô.
Entendi o meu problema é q é um exercicio q fala q uma pessoa diz q criou um metodo de ordenação q ordena qualqer grupo de 6 elementos em até 8 comparações,só q como o minimo quando trata de comparações é nlogn o valor de comparações vai chegar próximo a 12 pq 6log6 na base dois é maior q oito então isso ja falaria q a situação é uma mentira
mas mesmo assim vlw
Quando se escreve O(n log n) não quer dizer que o número de operações é exatamente n log n, mas sim que o número de operações é proporcional a n log n.
Se um determinado algoritmo leva 2,5 * n * log10 n operações, então ele é O (n log n).
Se outro algoritmo leva 4,7 * n * log2 n, ele também é O (n log n).
OK?
Portanto, não faz sentido dizer que log n é o logaritmo na base 2, ou na base 10, ou o logaritmo natural, nem faz sentido dizer que “com 6 elementos o máximo não pode ser 8 comparações mas não deve ser porque não está de acordo com a fórmula”. Lembrem-se que o número é proporcional, não igual, a n log n.