Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

fo_11

Que algoritmo de ordenacao escolher

Recommended Posts

fo_11

Tenho um trabalho a elaborar que uma das partes consiste na ordenação por bi de um array que pode atingir 100 mil pessoas, o que já é algo a considerável.

Estive a pesquisar e encontrei vários algoritmos de ordenação mas não sei qual o mais eficiente. Aqui fica a lista dos que encontrei (eles estão divididos em duas categorias):

Métodos simples:

Insertion sort

Selection sort

Bubble sort

Métodos sofisticados:

Quick sort

Merge sort

Heapsort

Shell sort

Radix sort

Gnome sort

Count sort

Bogosort

Bucket sort

Cocktail sort

Pelo que li estou mais virado para o algoritmo Quick sort o que pensam? Deverei usar outro? Não esquecer que o tamanho do array já não é muito pequeno.

Share this post


Link to post
Share on other sites
Strabush

Podes também ir experimentando cada um e calcular o tempo. Depois escolhes.

Share this post


Link to post
Share on other sites
M6

A eficiência depende de vários factores, há situações onde um determinado algoritmo é mais eficiente que os restantes.

Por isso não se pode dizer que há um mais eficiente que os outros.


10 REM Generation 48K!
20 INPUT "URL:", A$
30 IF A$(1 TO 4) = "HTTP" THEN PRINT "400 Bad Request": GOTO 50
40 PRINT "404 Not Found"
50 PRINT "./M6 @ Portugal a Programar."

 

Share this post


Link to post
Share on other sites
pedrosorio

Se souberes o range dos BI que vais receber e não for demasiado grande, podes implementar um counting sort que deve ser bastante eficiente.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
fo_11

O tamanho do bi varia muito pode ter apenas mil numeros como 100mil.

O Professor disponibilizou os ficheiros que iriamos usar para o programa e o mais pequeno tem os respectivos 1000 numeros de bi's e o maior 100 mil

Share this post


Link to post
Share on other sites
pedrosorio

pedrosorio: counting sort?

Sim, counting sort: http://en.wikipedia.org/wiki/Counting_sort

O tamanho do bi varia muito pode ter apenas mil numeros como 100mil.

O Professor disponibilizou os ficheiros que iriamos usar para o programa e o mais pequeno tem os respectivos 1000 numeros de bi's e o maior 100 mil

A questão não é quantos BI há, é saber qual é o BI menor e o BI maior.

P.S.: Faz upload do de 100.000 para testar se vale a pena counting sort.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
fo_11

Ok... Mas ainda está  com um pequeno problema... Se o vector já estiver ordenado e pedires para o programa o ordenar ele vai acabar por dar erro.

Foi a unica coisa que ainda não consegui resolver. Pelo que penso que seja por ele dividir em array de 1 elemento um array de 100mil elementos.

int PartitionAdn(PESSOA *id, int left, int right)                 //particao por adn    
{
        int i=left,j;

        for(j=left+1;j<=right;++j) 
          if(strcmp((id[j].adn),(id[left].adn))>0) 
            {++i;
             swap(&id[i], &id[j]);
            }
            
        swap(&id[left],&id[i]);
        return i;
}
void Quicksort(PESSOA *id, int left, int right,int flag_ord)             //flag_ord indica qual é o tipo de ordenacao que foi selecionado           
{
        int pivot;
         
        if(left < right) 
          {if(flag_ord==1)                                               //se flag_ord for 1 é ordenado por bi
             pivot=PartitionBi(id, left, right);
           else if(flag_ord==2)                                          //se for 2 é ordenado por adn
             pivot=PartitionAdn(id,left, right);      
           else                                                      //senão é por comprimento de adn
             pivot=PartitionAdnComp(id, left, right);
           Quicksort(id, left, pivot-1, flag_ord);
           Quicksort(id, pivot+1, right, flag_ord);
          }
}
void swap(PESSOA *id_1,PESSOA *id_2)                                 //efectuar troca, temos de copiar um campo de cada vez ao invez igualarmos de uma vez so, supondo que x e y sao do tipo PESSOA exemplo: x=y)
{
        PESSOA aux;
        aux.bi=(*id_1).bi;                                          //tem de ser escrito desta forma pois recebemos um apontador
        aux.adn=(*id_1).adn; 
        
        (*id_1).bi=(*id_2).bi;                                     
        (*id_1).adn=(*id_2).adn;
        
        (*id_2).bi=aux.bi;
        (*id_2).adn=aux.adn;
}

Obs: Isto é para um trabalho por isso à partes que terás que ignorar

Share this post


Link to post
Share on other sites
rafzk

metes uma flag para quando tiver ordenado! Quando faz o quicksort mete ordenado=1. E so faz a ordenacao se a flag estiver em 0. Tenta assim! :)

já tens uma flag para o tipo de ordenacao mas nao tens uma flag se o vector esta ordenado ou nao!

Share this post


Link to post
Share on other sites
fo_11

Sim eu já apliquei isso para evitar ordenações repetidas, isto é, selecionar a mesma opcao de ordenação varias vezes seguidas. O problema é que tenho vários tipos de ordenacao e dois deles por mero acaso ficam iguais por isso não posso utilizar flags.

Já tentei juntar o insertsort ao quick sort mas não estou a conseguir. O objectivo seria o quicksort tratar dos arrays de grandes dimensoes e o insertsort actuava quando o quicksort chegava ao ponto de ter arrays de pequenas dimensoes.

Share this post


Link to post
Share on other sites
Rui Carlos

Se souberes o range dos BI que vais receber e não for demasiado grande, podes implementar um counting sort que deve ser bastante eficiente.

E se eventualmente a diferença entre o mínimo e o máximo for grande (o que me parece provável), pode-se usar o Radix Sort (+Counting Sort).

No entanto, pelos teste que fiz há uns tempos, e apesar de o Radix Sort+Counting Sort ter complexidade linear, só em conjuntos muito grandes é que bate o QuickSort

Share this post


Link to post
Share on other sites
pedrosorio

E se eventualmente a diferença entre o mínimo e o máximo for grande (o que me parece provável), pode-se usar o Radix Sort (+Counting Sort).

No entanto, pelos teste que fiz há uns tempos, e apesar de o Radix Sort+Counting Sort ter complexidade linear, só em conjuntos muito grandes é que bate o QuickSort

É, e geralmente esses conjuntos muito grandes verificar-se-iam em problemas nos quais o mesmo valor pode repetir-se, que não é o caso dos BI, portanto Counting Sort não seria de facto a solução neste caso.


Não respondo a dúvidas por mensagem.

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

×

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.