Ir para o conteúdo
  • 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

Mensagens Recomendadas

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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."

 

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.