Ordenação de números

[Bruno Oliveira]

Mais um problema de treino pitónico! (depois de um exame de 2h30 de C++, sabe tão bem estar "livre" daquela cadeira e poder voltar ao Python! )

(Novamente, à semelhança do problema dos números trimórficos, este problema é para ser resolvido pelos newbies. Os pitonistas de serviço, como o Tharis, o Ivo, etc, poderão achá-lo desnecessário e até um pouco idiota, mas será certamente um óptimo desafio para os newbies)

Problema:

Desde o "nascimento" da computação, um dos problemas que causou (e, que, provavelmente ainda hoje causará) uma grande agitação entre os programadores/aficionados da programação, é um problema que tem um enunciado simples, e que, na prática, também tem uma solução simples (mas que não é uma das mais eficientes que por aí andam, obviamente.). Falo do problema de ordenação. O seu enunciado pode ser algo do género:

Dada uma lista de números inteiros fora de ordem, ordená-los por ordem crescente.

Desde miúdos que aprendemos a fazer isso na escola, mas verão que desenvolver um algoritmo, por mais simples que seja, para resolver computacionalmente este problema, não é assim tão simples.

Nota: o algoritmo que eu desenvolvi para este programa é muito simples e só funciona (em tempo "útil") para listas muito pequenas, com, no máximo, cerca de 5000 números... A ideia não é desenvolver um mergesort ou quicksort, que são populares, mas sim conseguir pensar numa maneira totalmente diferente e criar um algoritmo mais personalizado, para realizar a tarefa em mãos... Uma dica: usem listas!!

[joao_moreira]

Já consegui fazer um programa de 11 linhas... Não ponho aqui o código nem digo para já como fiz para deixar outros newbies a pensar.
Obrigado pelo exercício.

[jap]

E já agora, a propósito: conseguem implementar o algoritmo Quicksort numa só linha pitónica?

Desafio!

[Bruno Oliveira]

Hmm... Numa só linha tenho de pensar... lá vêm as lambda functions ao barulho

Vou tentar arranjar um tempo no meio do meu estudo de Análise, para pensar sobre esse desafio . É desta que domino as lambda functions!!

[jap]

Hmm... Numa só linha tenho de pensar... lá vêm as lambda functions ao barulho

Vou tentar arranjar um tempo no meio do meu estudo de Análise, para pensar sobre esse desafio . É desta que domino as lambda functions!!

Não quero sentir-me culpado por prejudicar o teu estudo de Análise!

[Tharis]

:lol:

E já agora, a propósito: conseguem implementar o algoritmo Quicksort numa só linha pitónica?

Desafio!

Código: Seleccionar Todos

qsort = lambda l: l if len(l) <= 1 else qsort([i for i in l[1:] if i < l[0]]) + [l[0]] + qsort([i for i in l[1:] if i >= l[0]])

Não resisti ao one line challenge!

[Bruno Oliveira]

Hmm... Numa só linha tenho de pensar... lá vêm as lambda functions ao barulho

Vou tentar arranjar um tempo no meio do meu estudo de Análise, para pensar sobre esse desafio . É desta que domino as lambda functions!!

Não quero sentir-me culpado por prejudicar o teu estudo de Análise!

Não tem problema prof. , para o Python e para o Quark há sempre um tempinho , de qualquer forma, o Tharis não resistiu , parece que as lambda functions vão ser adiadas novamente...

[jap]

:lol:

E já agora, a propósito: conseguem implementar o algoritmo Quicksort numa só linha pitónica?

Desafio!

Código: Seleccionar Todos

qsort = lambda l: l if len(l) <= 1 else qsort([i for i in l[1:] if i < l[0]]) + [l[0]] + qsort([i for i in l[1:] if i >= l[0]])

Não resisti ao one line challenge!

Muito bem!

[Bruno Oliveira]

Bem, e como o Tharis já fez o one-liner, posso deixar aqui o meu método original, que usa duas listas.

A ideia é ir à lista dada pelo utilizador, procurar o valor minimo que ela tem, e adicioná-lo a uma outra lista. Após o valor minimo estar na nova lista, remove-se o valor minimo da antiga, e assim sucessivamente, até o tamanho da lista original ser 0.

Achei bastante interessante, pois não é nada de muito elaborado, é fácil de perceber e de escrever e usando o psyco funciona com listas até 10 000 números. Cá está então, o muito simples, código que mete por ordem uma lista de números:

Código: Seleccionar Todos

"""

Program that receives an unsorted list as user input, and returns as output
the list sorted in ascending order.

Bruno @2010 Having fun with Python.

"""

L = input('Input an unsorted list of real numbers: ')
J = []
while len(L) > 0:
    J.append(min(L))
    L.remove(min(L))
if len(L)==0:
    print "The sorted list is: ", J


[Tharis]

O algoritmo que descreveste é o Bubble Sort.

No entanto, o código que apresentaste está errado. Vê lá o que tens mal.

[Bruno Oliveira]

Corrigido

[Francisco_Lopes]

E para um newbie que não sabe mesmo nada de programação, por onde começa?

[Bruno Oliveira]

Bem, estar a postar isto aqui fica um bocado off-topic... mas, no problem .

Se não souberes nada de programação e quiseres começar a aprender Python, tanto para te divertires por aqui, como para desenvolveres as tuas capacidades de raciocino algorítmico, diria que tens um problema complicado entre mãos...Porque o que não falta por aí são livros e tutoriais excelentes.

Recomendo muito vivamente, qualquer dos links disponibilizados pelo prof. jap, que são excelentes e creio que, constantemente actualizados por serem afinal de contas, a documentação oficial... E, se calhar, numa opinião mais pessoal, não posso deixar de te referir o livro intitulado "How to think like a computer scientist: Learning with Python" do Engº Civil empregado na Google, Allen B. Downey É um excelente livro e tem os fundamentos explicados de uma forma que ainda não encontrei em mais lado nenhum, creio que te tornarás um excelente programmer se te guiares por esse livro

Abraço

[Tharis]

@Bruno Oliveira, tudo o que mencionaste está correcto e o que não falta são livros e tutoriais 5*, mas eu sou apologista do "learn and use".

Escrevendo a minha história com o Python em alguns caracteres: depois de decidir aprender Python, devorei uns bons livros de +-500 páginas e quando chegou a altura de fazer algo simples, não conseguia. Então, comecei a ler código de outros coders e a resolver desafios. Só posso dizer, valeu-me mais a segunda parte que ler todos os livros de Python do mundo. Claro que depois uma pessoa precisa sempre de uma referência particular a uma biblioteca ou paradigma, etc, mas para quem está a aprender, nada que um bom sistema de tutorial e desafio para isso.

@Francisco_Lopes, portanto, recomendo-te um projecto do DEI da UC (mais uma vez a UC está de Parabéns! ) que é o DEI Academy.


Cumprimentos
Tharis

[RicardoCampos]

Eu recomendo www.projecteuler.net/ com um tutorial de suporte.