Como encontrar os n menores números

[Késsia Nepomuceno 0]

Hey guys,

Eu tenho essa dúvida há um tempo

Como eu posso encontrar os n menores números de um conjunto de números e não o menor número.

Por exemplo:

Eu tenho esse número na entrada: 54621

E eu gostaria de saber quais são os três menores números.

- Agradeço qualquer ajuda!

[brhue 7]

@@Késsia Nepomuceno

 

 

Uma das alternativas seria, ordenar o conjunto em ordem crescente... exemplo...

num[5] = {2,4,5,1,3}

Você quer saber os três menores números.

Um simples bubble sort resolveria...

num[5] = {1,2,3,4,5} //vetor ordenado em ordem crescente.

Depois é só imprimir os 3 primeiros números do vetor num.

for (i=0; i<3; i++)
{ 
    printf("%d", num[i]);	   
}

Resultado: 123

 

 

brHUE

[Késsia Nepomuceno 0]

Oi @brhue

Eu tô tentando fazer por esse algoritmo, bubble sort, agora ;)

E meu código só funcionava na ordem crescente quando eu colocava um caso em ordem decrescente não funcionava então acho que o bubble sort vai ser ideal :D mas voce conhece outra maneira de fazer isso? Sem ser por esse algoritmo, só por curiosidade mesmo ^^

[GBecker 51]

Algorítimos de ordenação existem aos montes. Uns mais complicados e com melhor performance, outros mais simples e com menor performance. Cada caso de uso é um caso.

 

http://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o

[guidjos 65]

A estratégia de ordenar e retornar o enésimo elemento faz sentido e pode ser usada em grande parte dos cenários práticos.

 

Geralmente, os dados já estão ordenados e organizados de acordo com alguma estrutura de dados persistente, portanto o problema na prática tem solução trivial.

 

Se for preciso ordenar, a complexidade é O(n.logn). Nesse caso, a parte "demorada" da tarefa é a ordenação em si, que pode ser feita de inúmeras formas.

 

Um algoritmo icônico de ordenação é o quicksort - é simples de entender e razoavelmente fácil de implementar e aperfeiçoar. Aqui estão alguns exemplos de implementações minhas (em js): https://gist.github.com/guipn/3765097

 

Se os dados não couberem em memória (geralmente é o caso), aconselho usar um híbrido entre o mergesort e o quicksort:

 

1. Dividem-se os dados do(s) disco(s) conforme o mergesort, em pedaços que caibam na(s) memória(s)

2. Ordena-se, em cada memória, usando quicksort

3. Com as sublistas ordenadas por quicksort, usa-se a rotina de merge do mergesort

 

 

Esta é apenas uma das dezenas de estratégias possíveis, de que gosto por ser simples e intuitiva.

 

Aqui há implementações tanto do mergesort quanto do quicksort, também escritas por mim, e desta vez em Haskell: https://github.com/guipn/Hassort/blob/master/Hassort.hs

 

 

Voltando ao problema original: é o de se calcular estatísticas de ordem. O MIT fornece uma aula excelente sobre o assunto: http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-four/

 

Ali, comentam sobre a solução trivial envolvendo ordenação, para depois fornecer algoritmos alternativos (inclusive um que tem complexidade linear). O último algoritmo, conforme consta na descrição da aula, vem deste paper: http://www.catonmat.net/blog/wp-content/uploads/2008/08/time-bounds-for-selection.pdf

 

 

Espero ter ajudado.