Compartilhe
Ver o tópico anteriorIr em baixoVer o tópico seguinte
avatar
Admin
Admin
Mensagens : 5
Pontos : 17
Reputação : 2
Data de inscrição : 05/05/2017
Idade : 27
Localização : Bandeirantes
Ver perfil do usuário

MergeSort - Método de Ordenação

em Seg Nov 13, 2017 1:55 pm
Definição

Algoritmo de ordenação é baseado primeiramente em selecionar um elemento, dividir a lista e então, ordenar-las separadamente. E posteriormente há um processo complementar o qual é chamado de junção. O processo de Seleção e junção são complementares porque:
Seleção: divide a lista em 2 outras independentes. Junção: une 2 listas independentes em uma lista maior ordenada.

Isso insinua que o Mergesort consiste em duas chamadas recursivas e um processo de junção. Então, Mergesort é um algoritmo recursivo, que é implementado dividindo uma sequência original em pares de dados, ordena-as e depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes. Assim, sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas.
O mergeSort consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente.
Esta técnica realiza-se em três fases:
1 - Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.
2 - Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
3 - Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, O(nlogn).

Figura 1. Esquema de funcionamento do MergeSort

Performances:
Melhor caso: O(N log N).
Pior caso (raro): O(N log N).

Operações do Algoritmo

Função Intercala
Código:

void intercala(int *X, int ini, int fim, int meio){
    int poslivre, ini_v1, ini_v2, i, aux[10];
    ini_v1=ini;
    ini_v2=meio+1;
    poslivre=ini;
    while(ini_v1<=meio && ini_v2<=fim){
        if(X[ini_v1]<=X[ini_v2]){
            aux[poslivre]=X[ini_v1];
            ini_v1++;
        }
        else{
            aux[poslivre]=X[ini_v2];
            ini_v2++;
        }
        poslivre++;
    }

    for(i=ini_v1; i<=meio; i++){
        aux[poslivre]=X[i];
        poslivre++;
    }
    for(i=ini_v2; i<=fim; i++){
        aux[poslivre]=X[i];
        poslivre++;
    }

    for(i=ini; i<=fim; i++){
        X[i]=aux[i];
    }
}

Função de Ordenação
Código:

void merge(int *X, int ini, int fim){
   int meio;
   if(ini<fim){
     meio=(int)floor((ini+fim)/2);
     merge(X, ini, meio);
     merge(X, meio+1, fim);
     intercala(X, ini, fim, meio);
   }
}

Main
Código:

int main()
{
    int X[10], i;
    for(i=0; i<10; i++){
        printf("\nDigite o %do elemento:   ", i+1);
        scanf("%d",&X[i]);
    }

    printf("\n\n Desordenado");

    for(i=0; i<10; i++)  printf("\t%d", X[i]);
    merge(&X[0], 0, 9);
    printf("\n\n Ordenado");

    for(i=0; i<10; i++)  printf("\t%d", X[i]);

    return 0;
}

Videos para reforços ( ABRA OS SPOILERS )

MergeSort Método de Ordenação:



ATIVIDADE DE FIXAÇÃO ( ABRA O SPOILER )
Spoiler:

Clique "Questionário" para responder \/ :
Questionário
Ver o tópico anteriorVoltar ao TopoVer o tópico seguinte
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum