Jump to content
programmer1337

[Resolvido] Ordenaçao de Listas

Recommended Posts

programmer1337

Boas pessoal

Preciso de fazer a ordenaçao de uma lista com a maxima rapidez possivel e estava a pensar em utilizar algo como o MergeSort ou o QuickSort...

Gostaria que me dissessem se e possivel adaptar estes algoritmos para listas, ou se conhecem um metode melhor para a organizaçao das mesmas.

Obrigado ;)

CUMPS

Share this post


Link to post
Share on other sites
Diutsu

Primeiro, embora de não grande importancia: as listas são simplesmente ligadas ou duplamente?

É possivel aplicares qualquer um desses algoritmos a listas, tens de ter em atenção que aceder a uma poslção n da lista implica que tens de percorrer a lista toda até chegares a essa posição. Pelo que vais ter de minimizar este factor, na implementação do teu algoritmo.

A eficiencia do algoritmo vai depender não só do algoritmo escolhido, bem como do tipo de dados que queres ordenar, e a variedade de dados que existem, isto se estiveres à procura de rapidez máxima.


XX SINFO - Semana Informática

Share this post


Link to post
Share on other sites
yyajsayy

Não tens muitas possibilidades..

Ou crias um array de ponteiros, onde um índice do array corresponde a um elemento da lista, e utilizas o qsort nesse array ou usa o mergesort que é o mais eficiente nas listas que faz é O(nlogn) tal como o qsort..


"If it don't work the first time, rename it to version 1.0."

http://seguranca-informatica.pt

Share this post


Link to post
Share on other sites
Cynary

Depende do tipo de lista.

Se estás a usar uma lista ligada, aconselho o quicksort, pois bem implementado não faz grande diferença (se alguma!) em relação a ordenar um array, e assim terá uma média de complexidade O(nlogn).

O merge sort também apresentará uma diferença pequena quando usado em listas ligadas em comparação com arrays normais, mas penso que fará uma maior diferença, pois em cada passo, além de juntar os dois arrays, ainda tens de percorrer a lista até ao meio (no entanto, isto é cortado quando representamos complexidade), o que fará em princípio que seja em média menos eficiente que o quicksort. No entanto, a complexidade é constante em O(nlogn).

Para melhorar o quicksort, aconselhar-te-ia a manter um ponteiro para o último elemento da lista.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.